[bzoj3998]弦论

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 500005
 4 int V,last,k,sum,a[N<<1],sz[N<<1],id[N<<1],ans[N<<1],len[N<<1],fa[N<<1],ch[N<<1][31];
 5 char s[N];
 6 void add(int c){
 7     int p=last,np=last=++V;
 8     len[np]=len[p]+1;
 9     sz[np]=1;
10     for(;(p)&&(!ch[p][c]);p=fa[p])ch[p][c]=V;
11     if (!p)fa[np]=1;
12     else{
13         int q=ch[p][c];
14         if (len[q]==len[p]+1)fa[np]=q;
15         else{
16             int nq=++V;
17             len[nq]=len[p]+1;
18             memcpy(ch[nq],ch[q],sizeof(ch[q]));
19             fa[nq]=fa[q];
20             fa[q]=fa[np]=nq;
21             for(;(p)&&(ch[p][c]==q);p=fa[p])ch[p][c]=nq;
22         }
23     }
24 }
25 int main(){
26     int t,k;
27     scanf("%s%d%d",s,&t,&k);
28     V=last=1;
29     for(int i=0;s[i];i++)add(s[i]-‘a‘);
30     for(int i=1;i<=V;i++)a[len[i]]++;
31     for(int i=1;s[i-1];i++)a[i]+=a[i-1];
32     for(int i=V;i;i--)id[a[len[i]]--]=i;
33     for(int i=V;i;i--)sz[fa[id[i]]]+=sz[id[i]];
34     if (!t)
35         for(int i=1;i<=V;i++)sz[i]=1;
36     memcpy(a,sz,sizeof(a));
37     sz[0]=a[0]=sz[1]=0;
38     for(int i=V;i;i--)
39         for(int j=0;j<26;j++)a[id[i]]+=a[ch[id[i]][j]];
40     if (a[1]<k){
41         printf("-1");
42         return 0;
43     }
44     for(int i=1;k>0;k-=sz[i])
45         for(int j=0;j<26;j++)
46             if (k>a[ch[i][j]])k-=a[ch[i][j]];
47             else{
48                 printf("%c",j+‘a‘);
49                 i=ch[i][j];
50                 break;
51             }
52 }