题目大意：
有n个字符串，编号为1~n，求每一个字符串在其他字符串中以它为后缀的字符串中编号第k小的字符串的编号。
思路：
将字符串倒过来建Trie，记录每个结尾节点的编号（可能会有重复，所以开一个vector记录）。再对trie树进行dfs序，记录结尾节点的子树区间。区间第k小，自然用可持久化线段树（由于权值就是id，所以不用离散化）。 注意：dfs序在遇到结尾节点时才++记录序号的变量cnt，而且相同串的dfs序号是一样的（就是说一个结尾节点可能包含好多个不同编号的串），左区间取最前的一个（比如dfs到x节点，编号为2，x节点存着两个串，那么它们的左区间都为2，而序号要加两次）
参考自：http://blog.csdn.net/xym_/article/details/51340321
代码：
1 #include<vector> 2 #include<cstdio> 3 #include<cstring> 4 #include<iostream> 5 #define M 500009 6 using namespace std; 7 vector <int> q[M]; 8 int cnt,trie[M][26],num[M],com[M],out[M],dat[M],sum[M<<2],lc[M<<2],rc[M<<2]; 9 char s[M]; 10 11 void ins(int id,char *str) 12 { 13 int i,l=strlen(str),j=0,k; 14 for (i=l-1;i>=0;i--,j=trie[j][k]) 15 if (!trie[j][k=str[i]-'a']) trie[j][k]=++cnt; 16 num[j]++; q[j].push_back(id); 17 } 18 19 void dfs(int x) 20 { 21 int i; 22 for (i=0;i<num[x];i++) com[q[x][i]]=cnt+1; 23 for (i=0;i<num[x];i++) dat[++cnt]=q[x][i]; 24 for (i=0;i<26;i++) if (trie[x][i]) dfs(trie[x][i]); 25 for (i=0;i<num[x];i++) out[q[x][i]]=cnt; 26 } 27 28 void build(int l,int r,int cur,int _cur,int x) 29 { 30 sum[cur]=sum[_cur]+1; 31 if (l==r) return; int mid=l+r>>1; 32 if (x<=mid) lc[cur]=++cnt,rc[cur]=rc[_cur],build(l,mid,lc[cur],lc[_cur],x); 33 else lc[cur]=lc[_cur],rc[cur]=++cnt,build(mid+1,r,rc[cur],rc[_cur],x); 34 } 35 36 int ask(int L,int R,int l,int r,int k) 37 { 38 if (L==R) return L; 39 int mid=L+R>>1,t=sum[lc[r]]-sum[lc[l]]; 40 if (t>=k) return ask(L,mid,lc[l],lc[r],k); 41 else return ask(mid+1,R,rc[l],rc[r],k-t); 42 } 43 44 int main() 45 { 46 int n,i,x; scanf("%d",&n); 47 for (i=1;i<=n;i++) scanf("%s",s),ins(i,s); 48 for (cnt=0,dfs(0),cnt=n+1,i=1;i<=n;i++) build(1,n,i+1,i,dat[i]); 49 for (i=1;i<=n;i++) 50 { 51 scanf("%d",&x); 52 if (sum[out[i]+1]-sum[com[i]]<x) printf("-1\n"); 53 else printf("%d\n",ask(1,n,com[i],out[i]+1,x)); 54 } 55 return 0; 56 }
转载于:https://www.cnblogs.com/HHshy/p/5738203.html
相关资源：JAVA上百实例源码以及开源项目