- 1#include 2#define N 200005 3#define LL long long 4 using namespace std;
- 5 const LL mo = 1000000007;
- 6 int F[27],
- a[N],
- rank[N],
- sa[N],
- h[N],
- g1[N],
- g2[N],
- next[N],
- n,
- m,
- ans,
- k,
- t,
- l,
- r,
- mid,
- x,
- y,
- z;
- 7 char S[N];
- LL f[N],
- w[N];
- 8 int oh(int k, int t, int p, int q) {
- 9 int l = 0,
- r = min(t - k, q - p) + 1,
- j;
- 10
- while (l < r) {
- 11 j = l + r + 1 >> 1;
- 12(f[k + j - 1] - f[k - 1] * w[j] % mo + mo) % mo == (f[p + j - 1] - f[p - 1] * w[j] % mo + mo) % mo ? 13 l = j: r = j - 1;
- 14
- }
- 15
- if (k + l > t) return 0;
- 16
- if (p + l > q) return 1;
- 17
- return a[k + l] > a[p + l];
- 18
- }
- 19 int jud(int u) {
- 20 int p,
- q,
- k,
- t;
- 21
- for (int i = n; i; --i) 22
- if (n - sa[i] + 1 - h[i] 1 - h[i]; 23
- else {
- p = sa[i];
- q = n - u + 1;
- break;
- }
- 24 t = n; k = 1; 25
- for (int i = n; i;) 26
- if (oh(i, t, p, q)) {
- 27
- if (i == t) return 0;
- 28 t = i; ++k;
- 29
- } else--i; 30
- if (k > m) return 0;
- return 1; 31
- }
- 32 int main() {
- 33 scanf("%d", &m);
- scanf("%s", S + 1);
- n = strlen(S + 1);
- 34 w[0] = 1;
- 35
- for (int i = 1; i <= n; ++i) {
- 36 a[i] = S[i] - 'a' + 1;
- 37 F[a[i]] = 1;
- 38 f[i] = (f[i - 1] * 29 + a[i]) % mo;
- 39 w[i] = w[i - 1] * 29 % mo;
- 40
- }
- 41
- for (int i = 2; i <= 26; ++i) F[i] += F[i - 1];
- 42
- for (int i = 1; i <= n; ++i) rank[i] = F[a[i]];
- t = F[26];
- 43
- for (int m = 1; m1) {
- 44
- for (int i = 1; i <= n; ++i) {
- 45 next[i] = g1[rank[i + m]];
- 46 g1[rank[i + m]] = i;
- 47
- }
- 48
- for (int i = t; i >= 0; --i) {
- 49
- for (int j = g1[i]; j; j = k) {
- 50 k = next[j];
- next[j] = g2[rank[j]];
- g2[rank[j]] = j;
- 51
- }
- 52 g1[i] = 0;
- 53
- }
- 54 z = 0;
- 55
- for (int i = 1; i <= t; ++i) {
- 56 y = -1;
- 57
- for (int j = g2[i]; j; j = k) {
- 58 k = next[j];
- next[j] = 0;
- 59
- if (y != rank[j + m]) y = rank[j + m],
- ++z;
- 60 h[j] = z;
- 61
- }
- 62 g2[i] = 0;
- 63
- }
- 64 t = z;
- 65
- for (int i = 1; i <= n; ++i) rank[i] = h[i];
- 66
- }
- 67
- for (int i = 1; i <= n; ++i) sa[rank[i]] = i,
- h[i] = 0;
- 68
- for (int i = 1; i <= n; ++i) 69
- if (rank[i] != 1) {
- 70 k = h[rank[i - 1]];
- if (k)--k;
- 71
- while (a[i + k] == a[sa[rank[i] - 1] + k])++k;
- 72 h[rank[i]] = k;
- r += n - i + 1 - k;
- 73
- }
- 74 l = 1; ++r;
- 75
- while (l < r) {
- 76 k = l + r + 1 >> 1;
- 77 jud(k) ? l = k: r = k - 1;
- 78
- }
- 79
- for (int i = n; i; --i) 80
- if (n - sa[i] + 1 - h[i] 1 - h[i]; 81
- else {
- k = sa[i];
- t = n - l + 1;
- break;
- }
- 82
- for (int i = k; i <= t; ++i) printf("%c", a[i] + 'a' - 1); 83
- return 0; 84
- }
来源: http://www.bubuko.com/infodetail-1955465.html