题目大意：
对于一个给定字符串，找到其所有不同的子串中排第k小的子串
先构建后缀自动机，然后我们可以将整个后缀自动机看做是一个DAG图，那么我们先进行拓扑排序得到 *b[N]
对于每个节点记录一个sc值，表示当前节点往下走可以得到不同的字符串的个数
然后从后往前，每次到达一个节点，当前节点sc赋1，然后每个可以往下走的son节点，都把这个son上的sc加到当前节点上即可
接下来得到一个排名，从root开始走，从a~z循环，通过sc正确的找到下一个进入的节点
#include <cstdio>
#include <iostream>
#include <cstring> using namespace std;
#define N 90005 struct SamNode{
int l , sc;
SamNode *son[] , *f;
}sam[N<<] , *root , *last , *b[N<<]; int cnt , num[N] , n , k;
char s[N];
void add(int x)
{
SamNode *p = &sam[++cnt] , *jp = last;
p->l = jp->l+;
last = p;
for(; jp&&!jp->son[x] ; jp=jp->f) jp->son[x] = p;
if(!jp) p->f = root;
else{
if(jp->l+ == jp->son[x]->l) p->f = jp->son[x];
else{
SamNode *r = &sam[++cnt] , *q = jp->son[x];
*r = *q; r->l = jp->l+;
p->f = q->f = r;
for( ; jp&&jp->son[x]==q ; jp=jp->f) jp->son[x] = r;
}
}
} void build()
{
int len = strlen(s);
for(int i= ; i<len ; i++) add(s[i]-'a');
for(int i= ; i<=cnt ; i++) num[sam[i].l]++;
for(int i= ; i<=len ; i++) num[i]+=num[i-];
for(int i= ; i<=cnt ; i++) b[--num[sam[i].l]] = &sam[i]; for(int i=cnt ; i>= ; i--){
b[i]->sc=;
for(int j= ; j< ; j++){
if(b[i]->son[j])
b[i]->sc+=b[i]->son[j]->sc;
}
}
} void solve()
{
scanf("%d" , &n);
char tmp[N];
int val , t;//t表示tmp中的位数
while(n--){
scanf("%d" , &k);
SamNode *cur = root;
val = , t=;
while(val<k){
for(int i= ; i< ; i++){
if(cur->son[i]){
if(val+cur->son[i]->sc<k) val+=cur->son[i]->sc;
else{
val++;
tmp[t++] = i+'a';
cur = cur->son[i];
break;
}
}
}
}
tmp[t]='\0';
printf("%s\n" , tmp);
}
} int main()
{
// freopen("a.in" , "r" , stdin);
scanf("%s" , s);
root = last = &sam[cnt=];
build();
solve();
return ;
}