bzoj 3998 [TJOI2015]弦论

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

题解

先对这个串建个SAM，再对所有节点按照max排下序。这样就可以从长到短地总结答案。

首先对每个节点维护一个当前节点所占的子串个数。假如t=1就按照Parent树里从叶子节点一层一层往上推的顺序，计算每个串出现的次数。t=0就不用管，直接设成1

这样就可以维护出每个节点往后推会有多少个串。。（直接加起来

然后在SAM上按照字典序往下匹配就可以了

#include <cstdio>
#include <cstring>
#define N 500010
using namespace std;
int dis[N<<1],fa[N<<1],siz[N<<1],ch[N<<1][26],sz=1,root=1,last=root,len,t,k;
char s[N];
void insert(int x)
{
    int pre=last,now=++sz;last=now;
    dis[now]=dis[pre]+1;siz[now]=1;
    for (;pre && !ch[pre][x];pre=fa[pre]) ch[pre][x]=now;
    if (!pre) fa[now]=root;
    else
    {
        int q=ch[pre][x];
        if (dis[q]==dis[pre]+1)
            fa[now]=q;
        else
        {
            int nows=++sz;dis[nows]=dis[pre]+1;
            fa[nows]=fa[q],fa[now]=fa[q]=nows;
            memcpy(ch[nows],ch[q],sizeof ch[q]);
            for (;pre && ch[pre][x]==q;pre=fa[pre]) ch[pre][x]=nows;
        }
    }
}
int ton[N<<1],ti[N<<1],sum[N<<1];
void work()
{
    for (int i=1;i<=sz;i++) ton[dis[i]]++;
    for (int i=1;i<=len;i++) ton[i]+=ton[i-1];
    for (int i=1;i<=sz;i++) ti[ton[dis[i]]--]=i;
    for (int i=sz;i;i--)
        if (t) siz[fa[ti[i]]]+=siz[ti[i]];
        else siz[ti[i]]=1;
    siz[root]=0;
    for (int i=sz;i;i--)
    {
        sum[ti[i]]=siz[ti[i]];
        for (int j=0;j<26;j++)
            if (ch[ti[i]][j])
                sum[ti[i]]+=sum[ch[ti[i]][j]];
    }
}
main()
{
    scanf("%s%d%d",s+1,&t,&k);len=strlen(s+1);
    for (int i=1;i<=len;i++) insert(s[i]-'a');
    work();
    if (k>sum[root])    return puts("-1"),0;
    int now=root;
    while((k-=siz[now])>0)
    {
        int p=0;
        while(k>sum[ch[now][p]]) k-=sum[ch[now][p++]];
        now=ch[now][p];
        putchar('a'+p);
    }
}