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