题面
如果要求的是第k小字串(即连续子序列)，是可以用后缀自动机做的
然而这道题要求第k小子序列
其实序列自动机也是有的，而且构建及其简单
状态有$n+1$个，第一个为根，后面的和字符串每一位一一对应
对于第$i$位对应的状态，接收字符$c$后转移到$j$ 满足
说人话就是最近的一个$c$
感性的理解:我从最前面一个走就能涵盖从后面走的所有情况
然后这个自动机上每一条从根出发的路径唯一对应一个子序列(不重复)
于是求出每个状态能到达的子序列数(也就是从该点出发的路径数)，然后扫一遍即可(不会的话可以参考后缀自动机的做法)
注意一下路径数可能会很大很大，不需要高精，如果一个节点对应的路径数超过$k$，那么超过部分显然没有意义，直接赋为$k$即可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
using namespace std;
int son[1000010][26], n, k;
int tot[1000010];
char s[1000010];
int main() {
scanf("%d%d", &n, &k);
scanf("%s", s + 1);
for(int i = n - 1; i >= 0; i--) {//构建序列自动机
memcpy(son[i], son[i + 1], sizeof(int[26]));
son[i][s[i + 1] - 'a'] = i + 1;
}
for(int i = n; i >= 0; i--) {//0到n为天然的拓扑序
long long ans = 1;
for(int j = 0; j < 26; j++) ans += tot[son[i][j]];//计算路径数
tot[i] = min(ans, (long long)k);//如果过大就钦定为k
}
k++;//这种做法会算上空序列
for(int now = 0; ;) {
k -= 1;//去掉空序列(最小)
if(k == 0) return 0;
for(int j = 0; j < 26; j++) {
if(son[now][j] == 0) continue;
if(k > tot[son[now][j]]) k -= tot[son[now][j]];
else {
putchar(j + 'a');
now = son[now][j];
break;//转换为子问题
}
}
}
}