【BZOJ-3998】弦论后缀自动机

3998: [TJOI2015]弦论

Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 2018 Solved: 662
[Submit][Status][Discuss]

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

Source

Solution

后缀自动机的裸题？不过给我挺大帮助的。

建出后缀自动机求K大的问题，先拓扑排序/基数排序，然后递推出每个节点能到的子串数，然后dfs一遍加加减减。

这个题在递推的时候讨论一下即可，T=0时说明每个状态代表一个子串(除空串以外)，T=1时每个节点的Parent树的子树中的节点数都是可以得到的子串数，所以需要累加。

而这个累加的过程，可以理解成是求出$Right$集合的大小，所以构建时的新建节点显然不能重复计算。

然后dfs一遍，类似于线段树上二分的思想，输出答案。

自己没有写递归的写法，直接用的while里非递归。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define MAXN 500010
char A[MAXN],ans[MAXN];
int N,T,K;
namespace SAM
{
    int son[MAXN<<1][27],par[MAXN<<1],len[MAXN<<1],root,last,sz,size[MAXN<<1];
    inline void Init() {root=sz=last=1;}
    inline void Extend(int c)
    {
        int cur=++sz,p=last;
        len[cur]=len[p]+1; size[cur]=1;
        while (p && !son[p][c]) son[p][c]=cur,p=par[p];
        if (!p) par[cur]=root;
        else
            {
                int q=son[p][c];
                if (len[p]+1==len[q]) par[cur]=q;
                else
                    {
                        int nq=++sz;
                        memcpy(son[nq],son[q],sizeof(son[nq]));
 
                        len[nq]=len[p]+1;
                        par[nq]=par[q];
                        while (p && son[p][c]==q) son[p][c]=nq,p=par[p];
                        par[cur]=par[q]=nq;
                    }
            }
        last=cur;
    }
    inline void Build() {Init(); for (int i=1; i<=N; i++) Extend(A[i]-'a'+1);}
    int st[MAXN],id[MAXN<<1],sum[MAXN<<1];
    inline void Pre()
    {
        for (int i=1; i<=sz; i++) st[len[i]]++;
        for (int i=1; i<=N; i++) st[i]+=st[i-1];
        for (int i=1; i<=sz; i++) id[st[len[i]]--]=i;
        if (!T)
            {
                for (int i=sz; i>=1; i--) size[i]=1;
                size[root]=0;
                for (int i=sz,Sum=0; i>=1; i--,Sum=0)
                    {
                        for (int j=1; j<=26; j++)
                            Sum+=sum[son[id[i]][j]];
                        sum[id[i]]=Sum+1;
                    }
            }
        else
            {
                for (int i=sz; i>=1; i--)
                    size[par[id[i]]]+=size[id[i]];
                size[root]=0;
                for (int i=sz; i>=1; i--)
                    {
                        sum[id[i]]=size[id[i]];
                        for (int j=1; j<=26; j++)
                            sum[id[i]]+=sum[son[id[i]][j]];
                    }
            }
    }
    inline void Query(int K)
    {
        int now=root,tot=0;
        while (K)
            {
                for (int i=1; i<=26; i++)
                    if (son[now][i])
                        if (sum[son[now][i]]>=K)
                            {
                                ans[++tot]='a'+i-1;
                                K-=size[son[now][i]];
                                now=son[now][i];
                                break;
                            }
                        else K-=sum[son[now][i]];
 
            }
        ans[++tot]=0;
    }
}using namespace SAM;
int main()
{
    scanf("%s",A+1);
    N=strlen(A+1);
    SAM::Build();
    scanf("%d%d",&T,&K);
    SAM::Pre();
    if (sum[root]<K)
        puts("-1");
    else
        Query(K),puts(ans+1);
    return 0;
}