题目链接
题目解法
后缀自动机入门题。
建立后缀自动机。求第 (k) 大可以考虑按位确定。把后缀自动机当成一个 trie 树看，每次类似于平衡树上查找第 k 大的方式查找即可。
总结
没啥。
代码
#include <cstdio>
#include <cstring>
using namespace std;
const int CN = 5e5 + 5, CNODE = 1e6 + 5;
struct SAM {
int edge[26], parent, len, size;
bool leaf;
} node[CNODE];
int last, ntot, N, T, K, topo[CNODE], buc[CN], num[2][CNODE];
int cnt = 0;
void Extend(int c) {
++cnt;
int p = last, newnode = ++ntot;
node[newnode].len = node[last].len + 1;
//先计算 newnode的 len，再将 last变成 newnode
last = newnode;
node[newnode].leaf = 1;
for (; p && node[p].edge[c] == 0; p = node[p].parent) node[p].edge[c] = newnode;
if (!p)
node[newnode].parent = 1;
else {
int q = node[p].edge[c];
if (node[q].len == node[p].len + 1)
node[newnode].parent = q;
else {
int clone = ++ntot;
for (int i = 0; i < 26; ++i) node[clone].edge[i] = node[q].edge[i];
node[clone].leaf = 0;
// clone的 endpos
node[clone].parent = node[q].parent;
node[clone].len = node[p].len + 1;
node[q].parent = node[newnode].parent = clone;
for (; p && node[p].edge[c] == q; p = node[p].parent) node[p].edge[c] = clone;
}
}
}
void GetSize() {
for (int i = 1; i <= ntot; ++i) ++buc[node[i].len];
for (int i = 1; i <= N; ++i) buc[i] += buc[i - 1];
for (int i = 1; i <= ntot; ++i) {
topo[buc[node[i].len]--] = i;
node[i].size = node[i].leaf;
}
for (int i = ntot; i >= 1; --i) {
node[node[topo[i]].parent].size += node[topo[i]].size;
if (topo[i] != 1) {
num[0][topo[i]] = 1;
num[1][topo[i]] = node[topo[i]].size;
}
for (int j = 0; j < 26; ++j) {
if (node[topo[i]].edge[j]) {
num[0][topo[i]] += num[0][node[topo[i]].edge[j]];
num[1][topo[i]] += num[1][node[topo[i]].edge[j]];
}
}
}
}
void Find() {
int now = 1;
node[1].size = 0;
if (T == 0)
for (int i = 2; i <= ntot; ++i) node[i].size = 1;
num[T][1] = 0;
while (K > node[now].size) {
for (int i = 0; i < 26; ++i) {
if (!node[now].edge[i])
continue;
if (K <= num[T][node[now].edge[i]]) {
K -= node[now].size;
now = node[now].edge[i];
printf("%c", (char)i + 'a');
break;
} else
K -= num[T][node[now].edge[i]];
}
}
printf("
");
}
char str[CN];
int main() {
scanf("%s%d%d", str + 1, &T, &K);
N = strlen(str + 1);
last = ntot = 1;
for (int i = 1; i <= N; ++i) Extend(str[i] - 'a');
GetSize();
if (num[T][1] < K)
printf("-1
");
else
Find();
return 0;
}