A89666 题解

#include <bits/stdc++.h>
using namespace std;
const int N = 3e6 + 7;
int cnt[N], fst[N], sec[N], sa[N], height[N], rk[N];
int n, m, K;
char s[N];
template <typename T>inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; c < '0' || c > '9'; c = getchar())f |= (c == '-');
    for (; c >= '0' && c <= '9'; c = getchar())x = (x << 1) + (x << 3) + (c - '0');
    x = (f ? -x : x);
}
void get_sa() {
    for (int i = 1; i <= n; i++) {
        fst[i] = s[i];
        cnt[fst[i]]++;
    }
    for (int i = 2; i <= m; i++)cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; i--) {
        sa[cnt[fst[i]]] = i;
        cnt[fst[i]]--;
    }
    for (int k = 1;; k <<= 1) {
        int num = 0;
        for (int i = 1; i <= n; i++)sec[++num] = (sa[i] > k ? sa[i] - k : sa[i] - k + n);
        for (int i = 1; i <= m; i++)cnt[i] = 0;
        for (int i = 1; i <= n; i++)cnt[fst[i]]++;
        for (int i = 2; i <= m; i++)cnt[i] += cnt[i - 1];
        for (int i = n; i >= 1; i--) {
            sa[cnt[fst[sec[i]]]] = sec[i];
            cnt[fst[sec[i]]]--;
            sec[i] = 0;
        }
        swap(sec, fst);
        fst[sa[1]] = 1, num = 1;
        for (int i = 2; i <= n; i++) {
            if (sec[sa[i]] == sec[sa[i - 1]] && sec[sa[i] + k <= n ? sa[i] + k : sa[i] + k - n] == sec[sa[i - 1] + k <= n ? sa[i - 1] + k : sa[i - 1] + k - n])fst[sa[i]] = num;
            else fst[sa[i]] = ++num;
        }
        m = num;
        if (k >= n)break;
        if (m == n)break;
    }
    for (int i = 1; i <= n; i++)rk[sa[i]] = i;
}
typedef unsigned long long ULL;
ULL P[N], H[N];
const ULL base = 13331;
ULL get(int l, int r) {
    return H[r] - H[l - 1] * P[r - l + 1];}
int min_str() {
    int i = 0, j = 1, k = 0;
    char u, v;
    while (i < n && j < n && k < n) {
        u = s[(i + k) % n + 1], v = s[(j + k) % n + 1];
        if (u == v)++k;
        else {
            if (u > v)i += k + 1;
            else j += k + 1;
            k = 0;
            if (i == j)++i;
        }
    }
    return min(i, j);
}
char t[N];
int main() {
    read(n);
    read(K);
    scanf("%s", s + 1);
    int x = min_str() + 1;
    for (int i = 1; i <= n; ++i)t[i] = (x + i - 1 <= n ? s[x + i - 1] : s[x + i - 1 - n]);
    for (int i = 1; i <= n; ++i)s[i] = t[i];
    P[0] = 1;
    for (int i = 1; i <= n; i++)P[i] = P[i - 1] * base, H[i] = H[i - 1] * base + s[i];
    int R = n;
    for (int i = n - 1; i >= 1; i--) {
        if (get(1, i) == get(n - i + 1, n) && (n % (n - i) == 0)) {
            R = min(R, n - i);
        }
    }if (n / R >= K) {
        int c = n / R;
        int u = (1 - 1) % R + 1;
        int l = (c % K == 0 ? c / K : c / K + 1) * R;
        for (int i = u, j = 1; j <= l; j++, i = i % n + 1)putchar(s[i]);
        return 0;
    }m = 122;
    get_sa();
    for (int i = sa[K], j = 1; j <= n; j++, i = i % n + 1) {
        if (rk[i] < K)
            break;
        putchar(s[i]);
    }
    return 0;
}