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
| #include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int N = 2E5 + 100;
int last = 1, sz = 2, len[N], one[N], t[N][26], fa[N];
void ins(int ch, int pp) {
int p = last, np = last = sz++;
len[np] = len[p] + 1; one[np] = pp;
for (; p && !t[p][ch]; p = fa[p]) t[p][ch] = np;
if (!p) { fa[np] = 1; return; }
int q = t[p][ch];
if (len[q] == len[p] + 1) fa[np] = q;
else {
int nq = sz++; len[nq] = len[p] + 1; one[nq] = one[q];
memcpy(t[nq], t[q], sizeof t[0]);
fa[nq] = fa[q];
fa[q] = fa[np] = nq;
for (; p && t[p][ch] == q; p = fa[p]) t[p][ch] = nq;
}
}
char s[N];
int up[N], c[256] = {2}, a[N];
vector<int> G[N];
void rsort2() {
FOR (i, 1, 256) c[i] = 0;
FOR (i, 2, sz) up[i] = s[one[i] + len[fa[i]]];
FOR (i, 2, sz) c[up[i]]++;
FOR (i, 1, 256) c[i] += c[i - 1];
FOR (i, 2, sz) a[--c[up[i]]] = i;
FOR (i, 2, sz) G[fa[a[i]]].push_back(a[i]);
}
LL cnt[N], cc[N];
void dfs(int u) {
LL maxl = len[u], minl = len[fa[u]] + 1;
cnt[u] = (maxl + minl) * (maxl - minl + 1) / 2;
cc[u] = cnt[u];
for (int& v: G[u]) { dfs(v); cnt[u] += cnt[v]; }
}
void go(int u, LL k) {
if (k <= cc[u]) {
FOR (i, len[fa[u]] + 1, len[u] + 1) {
if (k > i) k -= i;
else {
putchar(s[one[u] + k - 1]);
return;
}
}
} else k -= cc[u];
for (int& v: G[u]) {
if (cnt[v] < k) k -= cnt[v];
else { go(v, k); return; }
}
}
int main() {
int T; cin >> T;
while (T--) {
scanf("%s", s);
int ll = strlen(s);
FORD (i, ll - 1, -1) ins(s[i] - 'a', i);
rsort2();
dfs(1);
dbg(cnt[1]);
LL K; cin >> K;
go(1, K);
puts("");
FOR (i, 0, sz + 10) G[i].clear();
memset(t, 0, (sz + 10) * sizeof t[0]);
last = 1; sz = 2;
}
}
|