【bzoj3998】弦论 后缀自动机

Description

对于一个给定长度为N的字符串，求它的第K小子串是什么。

Input

第一行是一个仅由小写英文字母构成的字符串S

第二行为两个整数T和K，T为0则表示不同位置的相同子串算作一个。T=1则表示不同位置的相同子串算作多个。K的意义如题所述。

Output

输出仅一行，为一个数字串，为第K小的子串。如果子串数目不足K个，则输出-1

Sample Input

aabc

0 3

Sample Output

aab

HINT

N<=5*10^5

T<2

K<=10^9

Sol

我们预处理sam上每个点按照拓扑序往后走一共几个串即可。

如果T=0，那么每个点初始权值都是1，否则按照拓扑序枚举点，然后把一个点的权值给他的pre节点累加。

之后在sam上跑26分即可。

Code

#include <bits/stdc++.h>

#define ll long long

using namespace std;

int T,n,K;char ch[500005];

struct SAM

{

    int tot,last,v[1000005],s[1000005],a[1000005][26],q[1000005],mx[1000005],fa[1000005],st[1000005];

    SAM(){last=++tot;}

    void ins(int c)

    {

        int p=last,np=last=++tot;mx[np]=mx[p]+1;v[np]=1;

        while(!a[p][c]&&p) a[p][c]=np,p=fa[p];

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

        else

        {

            int q=a[p][c];if(mx[p]+1==mx[q]) fa[np]=q;

            else

            {

                int nq=++tot;mx[nq]=mx[p]+1;memcpy(a[nq],a[q],sizeof(a[nq]));

                fa[nq]=fa[q];fa[q]=fa[np]=nq;

                while(a[p][c]==q) a[p][c]=nq,p=fa[p];

            }

        }

    }

    void pre()

    {

        for(int i=1;i<=tot;i++) st[mx[i]]++;

        for(int i=1;i<=n;i++) st[i]+=st[i-1];

        for(int i=tot;i;i--) q[st[mx[i]]--]=i;

        for(int i=tot;i;i--) if(T==1) v[fa[q[i]]]+=v[q[i]];else v[q[i]]=1;

        v[1]=0;

        for(int i=tot,j;i;i--) for(s[q[i]]=v[q[i]],j=0;j<26;j++) s[q[i]]+=s[a[q[i]][j]];

    }

    void dfs(int x,int K)

    {

        if(K<=v[x]) return;K-=v[x];

        for(int i=0;i<26;i++) if(a[x][i])

        {

            if(K<=s[a[x][i]]){putchar(i+'a');dfs(a[x][i],K);return;}

            K-=s[a[x][i]];

        }

    }

}sam;

int main()

{

    scanf("%s",ch+1);n=strlen(ch+1);scanf("%d%d",&T,&K);

    for(int i=1;i<=n;i++) sam.ins(ch[i]-'a');

    sam.pre();if(K>sam.s[1]) puts("-1");else sam.dfs(1,K);

}