题目链接：POJ 3693

我们定义一个字符串的重复数为最大的数字 $R$ 满足这个字符串可以被分割为 $R$ 个相同的连续子字符串。

给定一个长度为 $n$ 的字符串，你需要找到它的重复数最大的子串。如果有多个答案，输出字典序最小的子串。

数据范围：$1 \le n \le 10 ^ 5$。

Solution

枚举长度 $L$，然后求长度为 $L$ 的子串最多能连续出现多少次。这里只考虑至少出现 $2$ 次的情况。假设在原字符串中连续出现 $2$ 次，记这个字符串为 $T$，那么 $T$ 肯定包括了字符 $S_L, S_{2L}, S_{3L}, \cdots$ 中的某相邻的两个。所以只需要求 $\text{suffix}(i \cdot L), \text{suffix}((i + 1) \cdot L)$ 的最长公共前缀和 $\text{prefix}(i \cdot L - 1), \text{prefix}((i + 1) \cdot L - 1)$ 的最长公共后缀。后者可以将原串反转后求出 $\text{lcp}$。

如果 $\text{lcp}$ 与 $\text{lcs}$（姑且这么叫吧 QAQ）的长度和为 $K$，那么该子串出现了 $\left\lfloor\frac{K}{L}\right\rfloor + 1$ 次。

对于 $L \not \mid K$ 的情况，我们发现子字符串的左端点可以在一个长度为 $K \bmod L + 1$ 的区间内。我们只需要保证在重复次数最大的情况下，这段区间的内的 $rk(i)$ 的最小值最小，就能保证字典序最小了。

时间复杂度：$\mathcal O(n \log n)$，根据调和级数易证枚举复杂度正确。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 1e5 + 5, logN = 17;

int n, lg[N], f[N][logN];
char s[N];

template <int S>
struct SuffixArray {
    static const int N = S << 1;
    int n, m, a[N], sa[N], rk[N], bin[N], tmp[N], height[N], f[N][logN];
    void clear() {
        memset(a, 0, sizeof(a));
        memset(sa, 0, sizeof(sa));
        memset(rk, 0, sizeof(rk));
        memset(height, 0, sizeof(height));
    }
    void radixSort() {
        for (int i = 1; i <= m; i++) bin[i] = 0;
        for (int i = 1; i <= n; i++) bin[rk[i]]++;
        for (int i = 1; i <= m; i++) bin[i] += bin[i - 1];
        for (int i = n; i >= 1; i--) sa[bin[rk[tmp[i]]]--] = tmp[i];
    }
    template <class Tp>
    void build(Tp *_a, int _n, int _m) {
        n = _n, m = _m;
        std::copy(_a + 1, _a + n + 1, a + 1);
        for (int i = 1; i <= n; i++) rk[i] = a[i], tmp[i] = i;
        radixSort();
        for (int l = 1, p = 0; p < n; l <<= 1, m = p) {
            p = 0;
            for (int i = n - l + 1; i <= n; i++) tmp[++p] = i;
            for (int i = 1; i <= n; i++) if (sa[i] > l) tmp[++p] = sa[i] - l;
            radixSort();
            std::swap(rk, tmp);
            p = rk[sa[1]] = 1;
            for (int i = 2; i <= n; i++) {
                rk[sa[i]] = (tmp[sa[i - 1]] == tmp[sa[i]] && tmp[sa[i - 1] + l] == tmp[sa[i] + l]) ? p : ++p;
            }
        }
        for (int i = 1, k = 0; i <= n; i++) {
            k -= (k > 0);
            int j = sa[rk[i] - 1];
            for (; a[i + k] == a[j + k]; k++);
            height[rk[i]] = k;
        }
    }
    void buildST() {
        for (int i = 1; i <= n; i++) f[i][0] = height[i];
        for (int j = 1; (1 << j) <= n; j++) {
            for (int i = 1; i + (1 << j) - 1 <= n; i++) {
                f[i][j] = std::min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
            }
        }
    }
    int lcp(int l, int r) {
        l = rk[l], r = rk[r];
        if (l > r) std::swap(l, r);
        int k = lg[r - (++l) + 1];
        return std::min(f[l][k], f[r - (1 << k) + 1][k]);
    }
};

SuffixArray<N> A, B;

void buildST(int *a, int n) {
    for (int i = 1; i <= n; i++) f[i][0] = a[i];
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            f[i][j] = std::min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
    }
}
int query(int l, int r) {
    int k = lg[r - l + 1];
    return std::min(f[l][k], f[r - (1 << k) + 1][k]);
}
int main() {
    for (int i = 2; i < N; i++) lg[i] = lg[i >> 1] + 1;
    int cs = 0;
    while (~scanf("%s", s + 1) && s[1] != '#') {
        n = strlen(s + 1);
        A.build(s, n, 255), A.buildST();
        std::reverse(s + 1, s + n + 1);
        B.build(s, n, 255), B.buildST();
        std::reverse(s + 1, s + n + 1);
        buildST(A.rk, n);
        int mx = 0, rk = n + 1, ansl = 0, ansr = 0;
        for (int l = 1; l <= n; l++) {
            for (int i = 1, j = l + 1; j <= n; i += l, j += l) {
                int R = A.lcp(i, j), L = B.lcp(n - i + 2, n - j + 2);
                int k = L + R, cnt = k / l + 1;
                if (cnt > mx) mx = cnt, rk = n + 1;
                if (cnt == mx) {
                    int mn = query(i - L, i - L + k % l);
                    if (mn < rk) rk = mn, ansl = A.sa[mn], ansr = ansl + mx * l - 1;
                }
            }
        }
        printf("Case %d: ", ++cs);
        for (int i = ansl; i <= ansr; i++) putchar(s[i]);
        puts("");
    }
    return 0;
}