题意：求一个串的字典序第k小的子串/本质不同第k小的子串。
解：一开始我的想法是在后缀树上找，但是不知道后缀树上的边对应的是哪些字符...
然而可以不用fail树转移，用转移边转移即可。
先建一个后缀自动机，记忆化搜索每个节点向后向后有多少个串。
然后从起点开始向后一个字符一个字符的确定。
注意每到一个新点就要判断是否结束，并把k减去在此结束的串的个数。
#include <cstdio>
#include <cstring> const int N = ; int tr[N][], len[N], fail[N], siz[N], bin[N], cnt[N], topo[N];
int top, last; inline void init() {
top = last = ;
return;
} inline void insert(char c) {
int f = c - 'a';
int p = last, np = ++top;
last = np;
len[np] = len[p] + ;
cnt[np] = ;
while(p && !tr[p][f]) {
tr[p][f] = np;
p = fail[p];
}
if(!p) {
fail[np] = ;
}
else {
int Q = tr[p][f];
if(len[Q] == len[p] + ) {
fail[np] = Q;
}
else {
int nQ = ++top;
len[nQ] = len[p] + ;
fail[nQ] = fail[Q];
fail[Q] = fail[np] = nQ;
memcpy(tr[nQ], tr[Q], sizeof(tr[Q]));
while(tr[p][f] == Q) {
tr[p][f] = nQ;
p = fail[p];
}
}
}
return;
} inline void sort() {
for(int i = ; i <= top; i++) {
bin[len[i]]++;
}
for(int i = ; i <= top; i++) {
bin[i] += bin[i - ];
}
for(int i = ; i <= top; i++) {
topo[bin[len[i]]--] = i;
}
return;
} inline void count() {
for(int i = top; i >= ; i--) {
int x = topo[i];
cnt[fail[x]] += cnt[x];
}
return;
} char s[N]; int DFS(int x) {
if(siz[x]) {
return siz[x];
}
siz[x] = cnt[x];
for(int i = ; i < ; i++) {
if(tr[x][i]) {
siz[x] += DFS(tr[x][i]);
}
}
return siz[x];
} int main() {
scanf("%s", s + );
int n = strlen(s + );
init();
for(int i = ; i <= n; i++) {
insert(s[i]);
}
sort();
int flag, k;
scanf("%d%d", &flag, &k);
if(flag) {
count();
}
else {
for(int i = ; i <= top; i++) {
cnt[i] = ;
}
} int sum = ;
for(int i = ; i <= top; i++) {
sum += cnt[i] * (len[i] - len[fail[i]]);
} int p = ;
DFS(p);
if(k > sum) {
puts("-1");
return ;
}
cnt[] = ;
while() {
//printf("k = %d %d \n", k, k == 1);
if(k == ) {
break;
}
else {
k -= cnt[p];
}
//printf("k = %d p = %d \n", k, p);
for(int i = ; i < ; i++) {
if(!tr[p][i]) {
continue;
}
if(siz[tr[p][i]] >= k) {
putchar(i + 'a');
p = tr[p][i];
break;
}
else {
k -= siz[tr[p][i]];
}
}
} return ;
}
AC代码
又思考了一下，虽然记忆化搜索会搜到重复的节点，但是这些重复所表示的是到达它的不同方案，也就是它代表的不同子串。所以需要重复统计。
这样一个节点的一条转移边其实就是它下一个字符拼上f之后能形成的子串数。
感觉好神奇...