题意
给出一个字符串和q个询问，每个询问给出一个整数k，输出第k大得子串。
分析
建后缀自动机，利用匹配边来解决。设d[v]为从状态v开始有多少不同的路径。这个显然是可以递推出来的。然后对于每个询问，根据d[v]来选择走哪个状态就可以了。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 6 using namespace std; 7 const int maxn=2e5+100; 8 char s[maxn]; 9 struct state{ 10 int link,len; 11 int next[26]; 12 }st[2*maxn]; 13 int d[2*maxn]; 14 int n,last,cur,sz,Q; 15 void init(){ 16 sz=1; 17 last=cur=0; 18 st[0].link=-1; 19 st[0].len=0; 20 } 21 22 void build_sam(int c){ 23 cur=sz++; 24 st[cur].len=st[last].len+1; 25 int p; 26 for(p=last;p!=-1&&st[p].next[c]==0;p=st[p].link) 27 st[p].next[c]=cur; 28 if(p==-1) 29 st[cur].link=0; 30 else{ 31 int q=st[p].next[c]; 32 if(st[q].len==st[p].len+1) 33 st[cur].link=q; 34 else{ 35 int clone=sz++; 36 st[clone].len=st[p].len+1; 37 st[clone].link=st[q].link; 38 for(int i=0;i<26;i++) 39 st[clone].next[i]=st[q].next[i]; 40 for(;p!=-1&&st[p].next[c]==q;p=st[p].link) 41 st[p].next[c]=clone; 42 st[cur].link=st[q].link=clone; 43 } 44 } 45 last=cur; 46 } 47 int c[2*maxn]; 48 int cmp(int a,int b){ 49 return st[a].len>st[b].len; 50 } 51 void dp(){ 52 for(int i=0;i<sz;i++) 53 c[i]=i; 54 sort(c,c+sz,cmp ); 55 for(int i=0;i<sz;i++){ 56 int o=c[i]; 57 d[o]=1; 58 for(int j=0;j<26;j++){ 59 int v=st[o].next[j];; 60 if(v) 61 d[o]+=d[v]; 62 } 63 } 64 } 65 66 int main(){ 67 scanf("%s",s); 68 n=strlen(s); 69 init(); 70 for(int i=0;i<n;i++){ 71 int c=s[i]-'a'; 72 build_sam(c); 73 } 74 dp(); 75 scanf("%d",&Q); 76 for(int q=1;q<=Q;q++){ 77 int k,u=0; 78 scanf("%d",&k); 79 while(k>0){ 80 for(int i=0;i<26;i++){ 81 int v=st[u].next[i]; 82 if(v){ 83 if(k>d[v]) 84 k-=d[v]; 85 else{ 86 k--; 87 printf("%c",'a'+i); 88 u=v; 89 break; 90 } 91 } 92 } 93 } 94 printf(" "); 95 } 96 return 0; 97 }