传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3998
题目大意：对于一个给定长度为N的字符串，求它的第K小子串是什么。
题解：后缀自动机
我们可以这样想：1.从一个节点u开始到v1，v2两点，u,v1,v2在一条路径上，len值大的K值就更大，例如：aab<aabb;
2.从一个节点u开始到v1分开到v2，v3，那么u-->v1-->v2 && u-->v1---->v3的k值则由v1---v2和v1----v3决定。
所以我们就可以很容易进行比较大小，利用一下后缀自动机的树状结构，细节见代码。
代码：
1 #include<algorithm> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 #define maxn 1000005 7 using namespace std; 8 char s[maxn]; 9 int T,K; 10 int root,tot,last,m; 11 struct data{ 12 int sum[maxn],ssum[maxn],fa[maxn],son[maxn][26],val[maxn],ri[maxn],tmp[maxn],kkd; 13 int prepare(){last=root=tot=1;} 14 int newnode(int x) {val[++tot]=x; return tot;} 15 void extend(int x) 16 { 17 int p=last,np=newnode(val[p]+1);last=np; ri[np]=1; 18 for (; p && !son[p][x]; p=fa[p]) son[p][x]=np; 19 if (!p) fa[np]=root; 20 else 21 { 22 int q=son[p][x]; 23 if (val[q]==val[p]+1) fa[np]=q; 24 else 25 { 26 int nq=newnode(val[p]+1); 27 memcpy(son[nq],son[q],sizeof(son[q])); 28 fa[nq]=fa[q]; 29 fa[q]=fa[np]=nq; 30 for (; p && son[p][x]==q; p=fa[p]) son[p][x]=nq; 31 } 32 } 33 34 } 35 void pre() 36 { 37 for (int i=1; i<=tot; i++) sum[val[i]]++; 38 for (int i=1; i<=tot; i++) sum[i]+=sum[i-1]; 39 for (int i=tot; i; i--) tmp[sum[val[i]]--]=i; 40 for (int i=tot; i; i--) 41 { 42 int v=tmp[i]; 43 if (T==1) ri[fa[v]]+=ri[v]; 44 else ri[v]=1; 45 } 46 ri[1]=0; 47 for (int i=tot; i; i--) 48 { 49 int v=tmp[i]; ssum[v]=ri[v]; 50 for (int p=0; p<=25; p++) 51 ssum[v]+=ssum[son[v][p]]; 52 } 53 54 } 55 void build() 56 { 57 prepare(); 58 for (int i=1; i<=m; i++) extend(s[i]-'a'); 59 } 60 void dfs(int x,int k) 61 { 62 if (k<=ri[x]) return; 63 k-=ri[x]; 64 for (int i=0; i<=25; i++) 65 { 66 if (ssum[son[x][i]]>=k) 67 { 68 putchar(i+'a'); 69 dfs(son[x][i],k); 70 return ; 71 } 72 k-=ssum[son[x][i]]; 73 } 74 } 75 }SAM; 76 int main() 77 { 78 scanf("%s",s+1); m=strlen(s+1); 79 scanf("%d%d",&T,&K); 80 SAM.build(); 81 SAM.pre(); 82 if (K>SAM.ssum[root]) printf("-1"); 83 else SAM.dfs(root,K); 84 printf(" "); 85 return 0; 86 }
开始时间：20:40
结束时间：21:20