题目描述
给定一个字符串，求它的第 $k$ 小子串，$t=0$ 表示不同位置的相同子串算作一个，$t=1$ 表示不同位置的相同子串算作多个，无解输出 $-1$。
$n\le 5\times 10^5$，$t\in {0,1}$，$k\le 10^9$。
算法分析
利用后缀自动机的性质求解。
首先对字符串建立后缀自动机，求出每个节点的 $endpos$ 大小，即该状态表示的子串在原字符串中出现的次数。（若 $t=0$ 要单独置为 $1$）
$endpos$ 大小怎么求呢？首先再每插入一个字符时将新节点（叶子节点）的出现次数标记为 $1$，然后按照 $len$ 大小将所有节点基数排序，从大到小将子节点的出现次数累加进父节点即可。
这个基数排序的结果不但在后缀链接树上可以用，在状态转移图上也可以用，因为每次转移必定有转移后节点的 $len$ 不小于当前节点的 $len$。
再在状态转移图上以相同的方式统计每个节点能够转移到的子串个数，最后 $DFS$ 一遍选取第 $k$ 小的子串。
注意事项：
- 数组开两倍，不单是后缀自动机相关的数组，与后缀自动机节点数规模相同的数组也应当开两倍大小。
- 基数排序时累加和的枚举范围应当是 $[1,n]$，因为根节点的 $len$ 值为 $0$。
- 第一次基数排序再统计之后需要保证根节点的 $endpos$ 大小即在原字符串中的出现次数为 $0$，因为根节点并不表示任何一个子串。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include <cstdio>
#include <cstring>
#define N 500005
int ch[N<<1][26],fa[N<<1],len[N<<1],sz[N<<1],tot=1,lst=1;
inline void extend(char c) {
int p=lst,np=++tot;len[np]=len[p]+1;sz[np]=1;lst=np;
while(p&&!ch[p][c]) ch[p][c]=np,p=fa[p];
if(!p) fa[np]=1;
else {
int q=ch[p][c];
if(len[p]+1==len[q]) fa[np]=q;
else {
int nq=++tot;memcpy(ch[nq],ch[q],sizeof(ch[q]));
len[nq]=len[p]+1;fa[nq]=fa[q];fa[q]=fa[np]=nq;
while(p&&ch[p][c]==q) ch[p][c]=nq,p=fa[p];
}
}
}
char s[N];int c[N],res[N<<1],f[N<<1];
void solve(int x,int k) {
if(k<=sz[x]) putchar('\n');
else {
k-=sz[x];
for(register int i=0;i<26;++i) if(ch[x][i]) {
if(k<=f[ch[x][i]]) {putchar('a'+i);solve(ch[x][i],k);break;}
else k-=f[ch[x][i]];
}
}
}
int main() {
scanf("%s",s);int t,k,n=strlen(s);scanf("%d%d",&t,&k);
for(register int i=0;i<n;++i) extend(s[i]-'a');
for(register int i=1;i<=tot;++i) ++c[len[i]];
for(register int i=1;i<=n;++i) c[i]+=c[i-1];
for(register int i=1;i<=tot;++i) res[c[len[i]]--]=i;
for(register int i=tot;i>=2;--i) sz[fa[res[i]]]+=sz[res[i]];
f[1]=sz[1]=0;for(register int i=2;i<=tot;++i) f[i]=sz[i]=(t?sz[i]:1);
for(register int i=tot;i>=1;--i) for(register int j=0;j<26;++j)
if(ch[res[i]][j]) f[res[i]]+=f[ch[res[i]][j]];
if(k<=f[1]) solve(1,k);else puts("-1");
return 0;
}
|