[文章目录]
Description
对于一个给定长度为N的字符串，求它的第K小子串是什么。【两种定义：1.不同位置相同子串算一个。2.不同位置子串算多个】N<=2*10^5 K<=10^9
后缀自动机
我们对于字符串建一个后缀自动机，统计经过每个节点向下走路径个数，来判断向某个方向走或是停住。
对于不同位置算一个的定义，统计到每个节点向下走的路径个数，对于每个节点结束的个数为1，之后每个节点的个数等于自己的个数加上自己出边连向的点的路径个数。按照深度从大到小DP即可。
对于不同位置算不同子串的定义，统计每个节点的end_set的大小，为后缀树的子树中结束节点的个数【匹配到串上前缀结尾节点的个数】。将节点记录，最后树上递推一下即可得到答案。
另外，SAM的边数是O(3n)的，点数是O(2n)的。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 501000
char s[N],ans[N];
int n,t,k,last,ch[N<<1][26],dep[N<<1],pre[N<<1],tot,f[N<<1],r[N<<1];
void insert(int x)
{
int p=last,np=++tot;
last=np,dep[np]=dep[p]+1;
for(;p&&!ch[p][x];p=pre[p]) ch[p][x]=np;
if(!p) pre[np]=1;
else
{
int q=ch[p][x];
if(dep[q]==dep[p]+1) pre[np]=q;
else
{
int nq=++tot;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
dep[nq]=dep[p]+1,pre[nq]=pre[q],pre[q]=pre[np]=nq;
for(;p&&ch[p][x]==q;p=pre[p]) ch[p][x]=nq;
}
}
}
int main()
{
last=tot=1;
scanf("%s%d%d",s,&t,&k); n=strlen(s);
int i,j,p;
for(i=0;i<n;++i) insert(s[i]-'a');
static int ws[N<<1],sa[N<<1];
for(p=1,i=0;i<n;++i) p=ch[p][s[i]-'a'],r[p]++;
for(i=1;i<=tot;++i) ws[dep[i]]++;
for(i=1;i<=n;++i) ws[i]+=ws[i-1];
for(i=tot;i>=1;--i) sa[ws[dep[i]]--]=i;
if(t) { for(i=tot;i>=1;--i) r[pre[sa[i]]]+=r[sa[i]]; }
else { for(i=tot;i>=1;--i) r[i]=1; }
for(r[1]=0,i=tot;i>=1;--i)
{
f[sa[i]]=r[sa[i]];
for(j=0;j<26;++j) f[sa[i]]+=f[ ch[sa[i]][j] ];
}
// for(i=1;i<=tot;++i) printf("%d\n",r[i]);
if(f[1]<k) puts("-1");
else
{
int len=0;
p=1;
while(k>r[p])
{
k-=r[p];
for(j=0;j<26;++j)
{
if(k<=f[ch[p][j]]) {ans[len++]='a'+j; p=ch[p][j]; break;}
else k-=f[ch[p][j]];
}
}
ans[len]='\0';
printf("%s",ans);
}
return 0;
}