并不对劲的bzoj3998:loj2102:p3975:[TJOI2015]弦论

题目大意

对于一个给定的长度为n(\(n\leq5*10^5\))的字符串，

分别求出不同位置的相同子串算作一个、不同位置的相同子串算作多个时，它的第k(\(k\leq10^9\))小子串是什么

题解

建这个字符串的后缀自动机

先dp求出后缀自动机上每一个点能走到多少个字符串

然后从根节点出发，每次走连向dp值不超过k且尽可能大的点的边

代码

#include<algorithm>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<ctime>

#include<iomanip>

#include<iostream>

#include<map>

#include<queue>

#include<set>

#include<stack>

#include<vector>

#define rep(i,x,y) for(register int i=(x);i<=(y);++i)

#define dwn(i,x,y) for(register int i=(x);i>=(y);--i)

#define maxn 500001

#define maxm 1000001

#define int long long

using namespace std;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)&&ch!='-')ch=getchar();

    if(ch=='-')f=-1,ch=getchar();

    while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

    return x*f;

}

void write(int x)

{

    if(x==0){putchar('0'),putchar('\n');return;}

    int f=0;char ch[20];

    if(x<0)putchar('-'),x=-x;

    while(x)ch[++f]=x%10+'0',x/=10;

    while(f)putchar(ch[f--]);

    putchar('\n');

    return;

}

int ch[maxm][26],fa[maxm],rt,lst,cnt,t,n,fir[maxm],nxt[maxm*2],v[maxm*2],cntrd,in[maxm],q[maxm],tl,hd=1,len;

int rgt[maxm],sum[maxm],K;

char s[maxn],ans[maxn];

void ade(int u1,int v1){v[cntrd]=v1,nxt[cntrd]=fir[u1],fir[u1]=cntrd++;}

int gx(char c){return c-'a';}

void ext(int i)

{

    int p=lst,np=++cnt,val=gx(s[i]);sum[np]=i,lst=np,rgt[np]=1;

    for(;p&&!ch[p][val];p=fa[p])ch[p][val]=np;

    if(!p)fa[np]=rt;

    else

    {

        int q=ch[p][val];

        if(sum[q]==sum[p]+1)fa[np]=q;

        else

        {

            int nq=++cnt;

            sum[nq]=sum[p]+1,fa[nq]=fa[q],fa[q]=fa[np]=nq;

            memcpy(ch[nq],ch[q],sizeof(ch[q]));

            for(;p&&ch[p][val]==q;p=fa[p])ch[p][val]=nq;

        }

    }

}

int cmp(int x,int y){return sum[x]<sum[y];}

signed main()

{

    //freopen(".in","r",stdin);

    //freopen(".out","w",stdout);

    memset(fir,-1,sizeof(fir));

    scanf("%s",s+1);lst=rt=++cnt;

    t=read(),K=read(),n=strlen(s+1);

    rep(i,1,n)ext(i);

    rep(i,1,cnt)in[sum[i]]++;

    rep(i,1,n)in[i]+=in[i-1];

    rep(i,1,cnt)q[in[sum[i]]--]=i;

    dwn(i,cnt,1)rgt[fa[q[i]]]+=rgt[q[i]],in[i]=0;

    rep(i,1,cnt)

    {

        rep(j,0,25)if(ch[i][j])in[i]++,ade(ch[i][j],i);

        if(in[i]==0)q[++tl]=i;sum[i]=0;

    }

    if(!t)rep(i,2,cnt)rgt[i]=1;

    rgt[rt]=0;

    while(hd<=tl)

    {

        int u=q[hd++];sum[u]+=rgt[u];

        for(int k=fir[u];k!=-1;k=nxt[k])

        {

            sum[v[k]]+=sum[u],in[v[k]]--;

            if(in[v[k]]==0)q[++tl]=v[k];

        }

    }

    int u=rt;

    while(u&&K>rgt[u])

    {

        int tmp=rgt[u];int nx=0;

        rep(i,0,25)

        {

            int vv=ch[u][i];

            if(vv&&tmp+sum[vv]>=K){ans[++len]=i+'a';nx=1,u=vv,K-=tmp;break;}

            tmp+=sum[vv];

        }

        if(!nx){write(-1);return 0;}

    }

    printf("%s",ans+1);

    return 0;

}

巴特西

并不对劲的bzoj3998:loj2102:p3975:[TJOI2015]弦论

题目大意

题解

代码

最新文章

热门文章