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; }
|