题目链接：POJ 3261

农夫 John 发现他的奶牛的产奶量每天都在变化。经过进一步调查，他发现：虽然他不能预知未来的产奶量，但是每天的产奶量有一些规律。

为了进行更严格的研究，他发明了一种复杂的分类方案。他记录下了 $n$ 天内的产奶数据，第 $i$ 个产奶量样本被记录为 $a_i$。他希望找到最长的样本模式，其重复次数至少为 $k$ 次，模式之间可以重叠。

数据范围：$1 \le n \le 2 \times 10 ^ 4$，$0 \le a_i \le 10 ^ 6$，$2 \le k \le n$。

Solution

对于子串重复问题，我们首先想到后缀数组，对序列建立后缀数组并求出 $height$ 数组。

先二分答案把问题转化为判定性问题，接下来把 $height$ 数组进行分组，满足同一组内的 $height$ 都不小于二分长度。如果有任意一组的大小 $\ge k$ 那么就满足条件；否则无解。

时间复杂度：$\mathcal O(n \log n)$。

Code

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

const int N = 2e4 + 5;

int n, k, a[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];
    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;
        }
    }
};

SuffixArray<N> A;

void discretize() {
    static int b[N];
    std::copy(a + 1, a + n + 1, b + 1);
    std::sort(b + 1, b + n + 1);
    int sz = std::unique(b + 1, b + n + 1) - (b + 1);
    for (int i = 1; i <= n; i++) {
        a[i] = std::lower_bound(b + 1, b + sz + 1, a[i]) - b;
    }
}
bool check(int x) {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (A.height[i] < x) cnt = 1;
        else if (++cnt >= k) return true;
    }
    return false;
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    discretize();
    A.build(a, n, n);
    int l = 0, r = n, ans = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        check(mid) ? l = (ans = mid) + 1: r = mid - 1;
    }
    printf("%d\n", ans);
    return 0;
}