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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1000010, M = N * 2;
int n;
char str[N];
struct SAM {
int maxlen[M], trans[M][26], link[M], sz, last;
int cnt[M];
SAM() { sz = last = 1; }
void init() {
memset(maxlen, 0, sizeof maxlen);
memset(trans, 0, sizeof trans);
memset(link, 0, sizeof link);
memset(cnt, 0, sizeof cnt);
sz = last = 1;
}
void extend(int ch) {
int cur = ++sz, p = last;
maxlen[cur] = maxlen[p] + 1;
cnt[cur] = 1;
for(; p && !trans[p][ch]; p = link[p]) trans[p][ch] = cur;
if(!p) link[cur] = 1;
else {
int q = trans[p][ch];
if(maxlen[p] + 1 == maxlen[q]) link[cur] = q;
else {
int clone = ++sz;
maxlen[clone] = maxlen[p] + 1;
memcpy(trans[clone], trans[q], sizeof trans[clone]);
link[clone] = link[q];
for(; p && trans[p][ch] == q; p = link[p]) trans[p][ch] = clone;
link[cur] = link[q] = clone;
}
}
last = cur;
}
} sam;
int a[M], b[M], sum[M];
int T, k;
int main() {
scanf("%s%d%d", str, &T, &k);
for (int i = 0; str[i]; i++) sam.extend(str[i] - 'a');
// 基数排序->拓扑序
for(int i = 1; i <= sam.sz; i++) a[sam.maxlen[i]]++;
for(int i = 1; i <= sam.sz; i++) a[i] += a[i - 1];
for(int i = 1; i <= sam.sz; i++) b[a[sam.maxlen[i]]--] = i;
// dp
for(int i = sam.sz; i; i--) {
int u = b[i];
if (T == 1) sam.cnt[sam.link[u]] += sam.cnt[u];
else sam.cnt[u] = 1;
}
sam.cnt[1] = 0;
for (int i = sam.sz; i; i--) {
int u = b[i];
sum[u] = sam.cnt[u];
for (int j = 0; j < 26; j++) {
int v = sam.trans[u][j];
if (!v) continue;
sum[u] += sum[v];
}
}
// solve
if (k > sum[1]) puts("-1");
else {
int u = 1; // 初始状态(空串)
while (sam.cnt[u] < k) { // p状态集合中不够k个
k -= sam.cnt[u]; // 更新k,扩展一个字符到新状态中找第k小
for (int i = 0; i < 26; i++) {
int v = sam.trans[u][i];
if (sum[v] >= k) {// 这条路有解
putchar(i + 'a');
u = v; // 走过去
break; // 进入下一次选择
} else { // 当前状态v不够k个,需要其他字符来转移
k -= sum[v]; // v出发能形成得字符串都小于k,更新k;
}
}
}
puts("");
}
return 0;
}
|