题目链接：POJ 1743

我们用长度为 $n$ 的音符序列 $a_i$ 表示一段音乐旋律，我们定义一个子串是这段音乐的主题，当其满足如下条件：

• 长度至少为 $5$。
• 经过转化后的子串在这段音乐中的其他位置出现过。所谓转化，就是给这个子串的每个元素加上同一个整数。
• 与重复出现的另一个子串不相交。

求出这段音乐中主题的最长长度。如果没有主题，那么输出 $0$。

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

Solution

对于转化这个操作，我们可以通过差分消去；需要注意的是，差分后，我们要寻找的子串长度变为至少为 $4$ 了。

由于答案有单调性，我们考虑二分答案 $x$ 转为判定性问题。

按照套路，我们求出后缀数组后将 $height$ 数组分组，每组内的 $height$ 都需要满足 $\ge x$，这意味着这一组内的后缀都有一个长度不小于 $x$ 的公共前缀。

考虑如何处理不可重叠的问题。我们只需要记录每一组内 $sa(i)$ 的最大值和最小值。如果两者之差不小于 $x$ 则满足条件。

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

Code

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

const int N = 2e4 + 5;

int n, 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;

bool check(int x) {
    int mx = 0, mn = 0;
    for (int i = 2; i <= n; i++) {
        if (A.height[i] < x) mx = mn = A.sa[i];
        else {
            mx = std::max(mx, A.sa[i]);
            mn = std::min(mn, A.sa[i]);
            if (mx - mn >= x) return true;
        }
    }
    return false;
}
int main() {
    while (scanf("%d", &n) && n) {
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for (int i = 1; i < n; i++) a[i] = a[i + 1] - a[i] + 100;
        a[n--] = 0;
        A.clear();
        A.build(a, n, 200);
        int l = 4, r = n / 2, ans = -1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            check(mid) ? l = (ans = mid) + 1 : r = mid - 1;
        }
        printf("%d\n", ans + 1);
    }
    return 0;
}