【TJOI2015】【BZOJ3998】弦论

Description

Solution

后缀三姐妹都可以做这题。 我选择最短的。

后缀自动机

不会的参照后缀自动机学习小记 建出后缀自动机。 先对后缀自动机拓扑一下（其实是为了方便求构出的字符串的个数和right集合的个数），其实不用真的求拓扑序，把len排个序就好了，很显然len的顺序就是拓扑序。 然后求出当前这个状态right的集合的大小（表示这个状态的字符串出现了多少次）。 那么求答案一个dfs就可以了，但是可能会爆栈，所以打成非递归版的就可以了。

Code

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define fo(i,a,b) for(i=a;i<=b;i++) #define fod(i,a,b) for(i=a;i>=b;i--) using namespace std; const int maxn=500007; int i,j,l,tt,n,m,T,ans1,ans2,k; int last,num; struct node{ int fa,len,sum; int son[26]; }t[maxn*2]; char s[maxn*2]; int a[maxn*2],b[maxn*2],cc[maxn*2],p,np,q,nq; void extend(int c){ p=last,np=++num; t[np].len=t[p].len+1;np=num;cc[np]=1; while(p&&!t[p].son[c])t[p].son[c]=np,p=t[p].fa; if(!p)t[np].fa=1; else{ q=t[p].son[c]; if(t[p].len+1==t[q].len)t[np].fa=q; else{ nq=++num; t[nq]=t[q]; t[num].len=t[p].len+1; t[q].fa=t[np].fa=nq; while(p&&t[p].son[c]==q)t[p].son[c]=nq,p=t[p].fa; } } last=np; } int main(){ freopen("string.in","r",stdin); freopen("string.out","w",stdout); // freopen("fan.in","r",stdin); // freopen("fan.out","w",stdout); scanf("%s",s+1); scanf("%d%d",&tt,&k); n=strlen(s+1);num=last=1; fo(i,1,n)extend(s[i]-'a'); fo(i,1,num)a[t[i].len]++; fo(i,1,n)a[i]+=a[i-1]; fod(i,num,1)b[a[t[i].len]--]=i; fod(i,num,1){ int u=b[i]; if(tt)cc[t[u].fa]+=cc[u]; else cc[u]=1; } cc[1]=0; fod(i,num,1){ int u=b[i];t[u].sum=cc[u]; fo(j,0,25){ t[u].sum+=t[t[u].son[j]].sum; } } if(t[1].sum<k)printf("-1\n"); else{ int x=1; while(1){ if(k<=cc[x])return 0; k-=cc[x]; fo(i,0,25){ if(t[x].son[i]){ if(k<=t[t[x].son[i]].sum){ putchar('a'+i); x=t[x].son[i]; break; } k-=t[t[x].son[i]].sum; } } } } }