对于一个给定长度为N的字符串，求它的第K小子串是什么。

 第一行是一个仅由小写英文字母构成的字符串S

输出仅一行，为一个数字串，为第K小的子串。如果子串数目不足K个，则输出-1

 N<=5*10^5

 1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 const int mxn=1000010;10 char s[mxn];11 int T;12 struct SAM{13     int t[mxn*2][26];14     int fail[mxn*2],l[mxn*2],ct[mxn*2];15     int w[mxn*2],rk[mxn*2],smm[mxn*2];16     int S,last,cnt;17     void init(){S=last=cnt=1;return;}18     void add(int c){19         int p=last,np=++cnt;20         last=np;l[np]=l[p]+1;21 //      ct[np]++;22         for(;p && !t[p][c];p=fail[p])t[p][c]=np;23         if(!p){fail[np]=S;}24         else{25             int q=t[p][c];26             if(l[q]==l[p]+1)fail[np]=q;27             else{28                 int nq=++cnt;l[nq]=l[p]+1;29                 memcpy(t[nq],t[q],sizeof t[q]);30                 fail[nq]=fail[q];31                 fail[q]=fail[np]=nq;32                 for(;p && t[p][c]==q;p=fail[p])t[p][c]=nq;33             }34         }35         return;36     }37     void st(){38         int i,j;int len=strlen(s+1),now=S;39         for(i=1;i<=cnt;i++)w[l[i]]++;40         for(i=1;i<=len;i++)w[i]+=w[i-1];41         for(i=cnt;i;i--)rk[w[l[i]]--]=i;42         for(i=1;i<=len;i++){43             now=t[now][s[i]-‘a‘];44             ct[now]++;45         }46         for(i=cnt;i;i--){47             int to=rk[i];48             if(T==1)ct[fail[to]]+=ct[to];49             else ct[to]=1;50         }51         ct[1]=0;52         for(i=cnt;i;i--){53             smm[rk[i]]=ct[rk[i]];54             for(j=0;j<26;j++){55                 smm[rk[i]]+=smm[t[rk[i]][j]];56             }57         }58         return;59     }60     void solve(int u,int k){61         if(k<=ct[u])return;62 //      printf("u:%d k:%d\n",u,k);63         k-=ct[u];64         for(int j=0;j<26;j++){65             if(t[u][j]){66                 int v=t[u][j];67                 if(k<=smm[v]){68                     printf("%c",j+‘a‘);69                     solve(v,k);70                     return;71                 }72                 else k-=smm[v];73             }74         }75         return;76     }77 }sa;78 int n,k;79 int main(){80     int i,j;81     scanf("%s",s+1);82     n=strlen(s+1);83     scanf("%d%d",&T,&k);84     sa.init();85     for(i=1;i<=n;i++) sa.add(s[i]-‘a‘);86     sa.st();87 //  printf("%d\n",sa.smm[1]);88     if(sa.smm[1]<k)printf("-1\n");89     else sa.solve(1,k);90     return 0;91 }