SPOJ SUBLEX Lexicographical Substring Search （ 后缀自动机）
http://www.spoj.com/problems/SUBLEX/en/
题意：
给一个字符串，每次询问字典序第k大的不重复子串。
思路：
先做个拓扑dp，求出SAM上，一个状态到种态的路径数。
拓扑dp其实就是按照拓扑序的dp啦…
然后从SAM的初始态开始，每次字典序从小到大得贪心寻找。思想类似可持久化线段树求区间第k大。
1/* ***********************************************
2Author :111qqz
3Created Time :2017年11月08日 星期三 18时50分18秒
4File Name :sublex.cpp
5************************************************ */
6
7#include <bits/stdc++.h>
8#define PB push_back
9#define fst first
10#define sec second
11#define lson l,m,rt<<1
12#define rson m+1,r,rt<<1|1
13#define ms(a,x) memset(a,x,sizeof(a))
14typedef long long LL;
15#define pi pair < int ,int >
16#define MP make_pair
17
18using namespace std;
19const double eps = 1E-8;
20const int dx4[4]={1,0,0,-1};
21const int dy4[4]={0,-1,1,0};
22const int inf = 0x3f3f3f3f;
23#define MAXALP 26
24
25struct state
26{
27 int len, link, nxt[MAXALP];
28};
29const int N =3E5+7;
30state st[N*2];
31int sz, last,rt;
32char s[N];
33int cnt[2*N],a[2*N];//for radix sort
34int sum[2*N]; //表示状态i到终态的路径数
35void sa_init()
36{
37 sz = 0;
38 last = rt = ++sz;
39 st[1].len = 0;
40 st[1].link=-1;
41 ms(st[1].nxt,-1);
42 ms(cnt,0);
43}
44
45void sa_extend(int c)
46{
47 int cur = ++sz;
48 st[cur].len = st[last].len + 1;
49 memset(st[cur].nxt, -1, sizeof(st[cur].nxt));
50 int p;
51 for (p = last; p != -1 && st[p].nxt[c] == -1; p = st[p].link)
52 st[p].nxt[c] = cur;
53 if (p == -1) {
54 st[cur].link = rt;
55 } else {
56 int q = st[p].nxt[c];
57 if (st[p].len + 1 == st[q].len) {
58 st[cur].link = q;
59 } else {
60 int clone = ++sz ;
61 st[clone].len = st[p].len + 1;
62 st[clone].link = st[q].link;
63 memcpy(st[clone].nxt, st[q].nxt, sizeof(st[q].nxt));
64 for (; p != -1 && st[p].nxt[c] == q; p = st[p].link)
65 st[p].nxt[c] = clone;
66 st[q].link = st[cur].link = clone;
67 }
68 }
69 last = cur;
70}
71void query( int k) //思想类似可持久化线段树找第k大
72//因为我们注意到，对于某个状态的所有转移，转移是j后得到的状态的所有子串的字典序一定比转移是(j+1)后得到的状态的所有子串的字典序小。
73{
74 int now = rt;
75 while (k)
76 {
77 for ( int i = 0 ; i < 26 ; i++)//字典序从小到大寻找，找到的一定是字典序最小的。
78 if (st[now].nxt[i]!=-1)
79 {
80 if (sum[st[now].nxt[i]]>=k)
81 {
82 putchar(('a'+i));
83 k--;
84 now = st[now].nxt[i];
85 break;
86 }
87 else k-=sum[st[now].nxt[i]]; //类似权值线段树找第k大
88 }
89 }
90 putchar('\n');
91}
92
93int main()
94{
95 #ifndef ONLINE_JUDGE
96 freopen("./in.txt","r",stdin);
97 #endif
98 sa_init();
99 ms(sum,0);
100 scanf("%s",s+1);
101 int len = strlen(s+1);
102 for ( int i = 1 ; i <= len ; i++)
103 {
104 sa_extend(s[i]-'a');
105 }
106 // a simple radix sort
107 for (int i = 1 ; i <= sz ; i++) cnt[st[i].len]++;
108 for ( int i = 1 ; i <= len ; i++) cnt[i]+=cnt[i-1];
109 for (int i = 1 ; i <= sz ;i++) a[cnt[st[i].len]--] = i;
110// for ( int i = 1 ; i <= sz ; i++) printf("a:%d\n",a[i]);
111 //将len按照从大到小的顺序存入临时数组a，a[1]表示len最短的状态的标号
112 //
113 //
114 //从len最长的更新，就是按照拓扑序更新。
115 //正确性在于len越大的越靠近SAM上的终止态
116 for ( int i = sz ; i >=1 ; i--)
117 {
118 int num = 0 ;
119 for ( int j = 0 ; j < 26 ; j++) if (st[a[i]].nxt[j]!=-1)
120 num+=sum[st[a[i]].nxt[j]];
121
122 sum[a[i]] = num + 1; //到终态的路径数，等于其能到达的状态到终态的路径数之和sum+该状态到终态的路径数1.
123 }
124// for ( int i = 1 ; i <= sz ; i++) printf("sum:%d\n",sum[i]);
125 int q;
126 cin>>q;
127 while (q--)
128 {
129 int x;
130 scanf("%d",&x);
131 query(x);
132 }
133
134
135 #ifndef ONLINE_JUDGE
136 fclose(stdin);
137 #endif
138 return 0;
139}