Musical Theme(后缀数组)

题意：

n个数，选取一段子序列，满足以下条件：
1.长度至少为5
2.在数列中其他位置出现过(允许转置)
3.与其他位置出现的不重叠
转置：将恒定的正或负值添加到子序列上
例如：
n个数为1，2,3，4,5，6,7，8,9，10
12345是一段子序列，那6,7，8,9，10也是，因为前者加5等于后者，且两者没有重叠

题解：

人是傻的，完全不会。。。
虽然两段序列不相等，但是也是有关系的，他们的差分区间相同，也就是其两两之间的差值一样，这样题目就转化成不重叠的最长公共子串问题
可以用二分+后缀数组
我们将原数组前后相减得到的新数据做后缀数组
二分的check：
二分最大长度k
检查两个子串是否不想交且公共前缀>=k
顺序扫描height数组
(height反应的是相邻两个后缀的lcp长度)
把height>=k的放在一起统计(将公共前缀>=k满足条件的串放在一起)，这是为了实现公共前缀>=k

保证其中最大的sa - 最小的sa > k,说明两个子串的位置距离差大于k，这是为了保证不相交
（SA[i]排序第i的后缀的开始位置）

例如字符串=“aabaaaab'”
当k=2时，后缀分为四组
在这里插入图片描述
最长公共前缀不小于k 的两个后缀一定在同一组

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxm = 100005;
const int INF = 1e9 + 7;
int a[maxm], b[maxm], sa[maxm], s[maxm], Rank[maxm], id[maxm], Height[maxm];
int n, m;
void Rsort()
{
    for (int i = 0; i <= m; i++) s[i] = 0;
    for (int i = 1; i <= n; i++) s[Rank[id[i]]] ++;
    for (int i = 1; i <= m; i++) s[i] += s[i - 1];
    for (int i = n; i >= 1; i--) sa[s[Rank[id[i]]] --] = id[i];
}
int cmp(int *f, int x, int y, int w)
{
    return f[x] == f[y] && f[x + w] == f[y + w];
}
void suffix()
{
    for (int i = 1; i <= n; i++) Rank[i] = a[i], id[i] = i;
    m = 200, Rsort();
    for (int w = 1, p = 1, i; p < n; w += w, m = p)
    {
        for (p = 0, i = n - w + 1; i <= n; i++) id[++p] = i;
        for (i = 1; i <= n; i++) if (sa[i] > w) id[++p] = sa[i] - w;
        Rsort(), swap(Rank, id), Rank[sa[1]] = p = 1;
        for (i = 2; i <= n; i++) Rank[sa[i]] = cmp(id, sa[i], sa[i - 1], w) ? p : ++p;
    }
    int j, k = 0;
    for (int i = 1; i <= n; Height[Rank[i++]] = k)
        for (k = k ? k - 1 : k, j = sa[Rank[i] - 1]; a[i + k] == a[j + k]; k++);
}
int judge(int x)
{
    int mi = INF, mx = -INF;
    for (int i = 2;i <= n;i++)
    {
        if (Height[i] >= x)
        {
            mi = min(mi, min(sa[i], sa[i - 1]));
            mx = max(mx, max(sa[i], sa[i - 1]));
            if (mx - mi > x) return 1;
        }
        else mi = INF, mx = -INF;
    }
    return 0;
}
int main()
{
    int i, j, k, sum, ans;
    while (scanf("%d", &n), n != 0)
    {
        ans = 0;
        for (i = 1;i <= n;i++) scanf("%d", &b[i]);
        for (i = 1;i <= n;i++) a[i] = b[i] - b[i - 1] + 100;
        suffix();
        int l = 0, r = n * 2;
        while (r - l > 1)
        {
            int mid = (r + l) / 2;
            if (judge(mid)) l = mid, ans = mid;
            else r = mid;
        }
        if (ans >= 4) printf("%d\n", ans + 1);
        else printf("0\n");
    }
    return 0;
}