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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
| #include <bits/stdc++.h>
#define N 100005
#define fi first
#define se second
using namespace std;
typedef long long ll;
char s[N];
int n, m, k, sa[N], sa2[N], rnk[N], key[N], sum[N], height[N];
int st[N<<1][21];
inline bool ok(int *num, int a, int b, int l) {
return num[a] == num[b] && num[a+l] == num[b+l];
}
inline void suffix() {
int i, j, p;
for (i = 1; i <= m; i++) sum[i] = 0;
for (i = 1; i <= n; i++) sum[rnk[i]=s[i]]++;
for (i = 1; i <= m; i++) sum[i] += sum[i-1];
for (i = n; i >= 1; i--) sa[sum[rnk[i]]--] = i;
for (j = 1; j <= n; j <<= 1, m = p) {
for (p = 0, i = n - j + 1; i <= n; i++) sa2[++p] = i;
for (i = 1; i <= n; i++) if (sa[i] > j) sa2[++p] = sa[i] - j;
for (i = 1; i <= n; i++) key[i] = rnk[sa2[i]];
for (i = 1; i <= m; i++) sum[i] = 0;
for (i = 1; i <= n; i++) sum[key[i]]++;
for (i = 1; i <= m; i++) sum[i] += sum[i-1];
for (i = n; i >= 1; i--) sa[sum[key[i]]--] = sa2[i];
for (swap(sa2, rnk), i = 2, p = 2, rnk[sa[1]] = 1; i <= n; i++) {
rnk[sa[i]] = ok(sa2, sa[i-1], sa[i], j) ? p-1 : p++;
}
}
}
inline void geth() {
int p = 0;
for (int i = 1; i <= n; i++) {
int j = sa[rnk[i]-1];
if (p) p--;
while (s[i+p] == s[j+p]) p++;
height[rnk[i]] = p;
}
}
inline void init_st() {
for (int i = 1; i <= n; i++) st[i][0] = height[i];
for (int l = 1; l <= 20; l++) {
for (int i = 1; i + (1 << l) - 1 <= n; i++) {
st[i][l] = min(st[i][l-1], st[i+(1<<(l-1))][l-1]);
}
}
}
inline int LCP(int x, int y) {
if (x == y) return n - x + 1;
int l = rnk[x], r = rnk[y];
if (l > r) swap(l, r);
l++;
int len = log2(r - l + 1);
return min(st[l][len], st[r-(1<<len)+1][len]);
}
inline pair<int, int> getrnk(ll r) {
int i;
for (i = 1; i <= n && r > n - sa[i] - height[i] + 1; i++) {
r -= n - sa[i] - height[i] + 1;
}
return make_pair(sa[i], height[i] + r);
}
inline bool cmp(pair<int, int> a, pair<int, int> b) {
int lcp = LCP(a.fi, b.fi);
if (lcp >= a.se || lcp >= b.se) {
return a.se <= b.se;
} else return s[a.fi + lcp] < s[b.fi + lcp];
}
inline bool check(ll mid) {
pair<int, int> a = getrnk(mid);
int cnt = 0;
for (int i = n, lst = n; i >= 1; i--) {
if (s[a.fi] < s[i]) {
return false;
}
if (!cmp(make_pair(i, lst - i + 1), a)) {
cnt++, lst = i;
}
if (cnt >= k) {
return false;
}
}
return true;
}
int main() {
scanf("%d%s", &k, s+1); n = strlen(s+1); m = 128;
suffix(); geth();
ll tot = 0;
for (int i = 1; i <= n; i++) tot += n - sa[i] + 1 - height[i];
init_st();
ll l = 1, r = tot, mid, ans = tot;
while (l <= r) {
mid = (l + r) >> 1;
if (check(mid)) {
ans = mid; r = mid - 1;
} else l = mid + 1;
}
pair<int, int> aa = getrnk(ans);
for (int i = aa.fi; i <= aa.fi + aa.se - 1; i++) {
putchar(s[i]);
}
return 0;
}
|
