# BZOJ 3998: [TJOI2015] string theory [suffix automata]

#### Question:

For a given string of length N, find out what its K-th substring is.
Input
The first line is a lowercase only string S
The second line is two integers, t and K. if t is 0, the same substring at different positions is counted as one. T=1 means that the same substring at different positions is counted as multiple.
N<=500000

#### Topic analysis:

The magical nature of suffix automata..
If there are multiple points in different positions, then each point of the root node represents a string of its end points.
Calculate one in different positions, then each point represents a string (including the cloned points) except the root node.
It seems very reasonable to think about it

Code:

```#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 1000005
#define maxc 26
using namespace std;
const int inf = 0x3f3f3f3f;
int n,T,K,sum[maxn],b[maxn],sa[maxn];
char a[maxn];
int fail[maxn]={-1},ch[maxn][maxc],len[maxn],cnt[maxn],sz,last;
void sa_extend(int c){
int p=last,cur=++sz,q;
len[last=cur]=len[p]+1,cnt[cur]=1;
for(;p!=-1&&!ch[p][c];p=fail[p]) ch[p][c]=cur;
if(p==-1) fail[cur]=0;
else if(len[p]+1==len[q=ch[p][c]]) fail[cur]=q;
else{
int clone=++sz; len[clone]=len[p]+1,fail[clone]=fail[q];
fail[q]=fail[cur]=clone;
memcpy(ch[clone],ch[q],sizeof ch[q]);
for(;p!=-1&&ch[p][c]==q;p=fail[p]) ch[p][c]=clone;
}
}
int main()
{
scanf("%s",a+1),n=strlen(a+1);
for(int i=1;i<=n;i++) sa_extend(a[i]-'a');
scanf("%d%d",&T,&K);
for(int i=1;i<=sz;i++) b[len[i]]++;
for(int i=1;i<=n;i++) b[i]+=b[i-1];
for(int i=1;i<=sz;i++) sa[b[len[i]]--]=i;
for(int i=sz;i>=1;i--)
if(T) cnt[fail[sa[i]]]+=cnt[sa[i]];
else cnt[i]=1;
cnt[0]=0;
for(int i=sz,t;i>=0;i--){
t=sa[i],sum[t]=cnt[t];
for(int j=0;j<maxc;j++) if(ch[t][j]) sum[t]+=sum[ch[t][j]];
}
if(sum[0]<K) puts("-1");
else{
for(int p=0;K>0;K-=cnt[p])
for(int c=0,v;c<maxc;c++){
if(!(v=ch[p][c])) continue;
if(sum[v]<K) K-=sum[v];
else {putchar(c+'a'),p=v;break;}
}
}
}
```

Posted on Sat, 30 Nov 2019 20:32:39 -0800 by Seaholme