题目描述：

给你一个数字序列。

如果两个子序列满足：

1 长度相同

2 没有重叠

3 每个元素的差值相同

那么我们就认为这个两个子序列是个旋律。

问你最长的旋律是多长（至少有5的长度）

解题报告：

看题目描述很容易想到lcp，最长公共前缀问题。

转化方式如下：

原序列x0,x1...xn-1

两两求差值，得到序列

s0,s1,...sn-2

其中si = xi - xi+1

这样，s序列的不重复的最长公共子串就是答案。

最后答案要+1，因为m个差值是m+1个元素。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define N 2000006
int s[N];
int n, sa[4*N], rank[N], height[N];
int buf[4*N], ct[N], sx[N], sax[N];
inline bool leq(int a, int b, int x, int y)
{
    return (a < x || a == x && b <= y);
}
inline bool leq(int a, int b, int c, int x, int y, int z)
{
    return (a < x || a == x && leq(b, c, y, z));
}
inline int geti(int t, int nx, int sa[])
{
    return (sa[t]<nx ? sa[t]*3+1 : (sa[t]-nx)*3+2);
}
static void radix(int a[], int b[], int s[], int n, int k)
{ // sort a[0..n-1] to b[0..n-1] with keys in 0..k from s
    int i, t, sum;
    memset(ct, 0, (k + 1) * sizeof(int));
    for (i = 0; i < n; ++i) ct[s[a[i]]]++;
    for (i = 0, sum = 0; i <= k; ++i)
    {
        t = ct[i]; ct[i] = sum; sum += t;
    }
    for (i = 0; i < n; i++) b[ct[s[a[i]]]++] = a[i];
}
void suffix(int s[], int sa[], int n, int k)
{ // !!! require s[n] = s[n+1] = s[n+2] = 0, n >= 2.
    int i, j, e, p, t;
    int name = 0, cx = -1, cy = -1, cz = -1;
    int nx = (n+2)/3, ny = (n+1)/3, nz = n/3, nxz = nx+nz;
    int *syz = s + n + 3, *sayz = sa + n + 3;
    for (i=0, j=0; i < n + (nx - ny); i++)
    if (i%3 != 0) syz[j++] = i;
    radix(syz , sayz, s+2, nxz, k);
    radix(sayz, syz , s+1, nxz, k);
    radix(syz , sayz, s , nxz, k);
    for (i = 0; i < nxz; i++)
    {
        if (s[ sayz[i] ] != cx || s[ sayz[i] + 1 ] != cy ||s[ sayz[i] + 2 ] != cz)
        {
            name++; cx = s[ sayz[i] ];
            cy = s[ sayz[i] + 1 ]; cz = s[ sayz[i] + 2 ];
        }
        if (sayz[i] % 3 == 1) syz[ sayz[i] / 3 ] = name;
        else syz[ sayz[i]/3 + nx ] = name;
    }
    if (name < nxz)
    {
        suffix(syz, sayz, nxz, name);
        for (i = 0; i < nxz; i++) syz[sayz[i]] = i + 1;
    }
    else
    {
        for (i = 0; i < nxz; i++) sayz[syz[i] - 1] = i;
    }
    for (i = j = 0; i < nxz; i++)
    if (sayz[i] < nx) sx[j++] = 3 * sayz[i];
    radix(sx, sax, s, nx, k);
    for (p=0, t=nx-ny, e=0; e < n; e++)
    {
        i = geti(t, nx, sayz); j = sax[p];
        if ( sayz[t] < nx ?leq(s[i], syz[sayz[t]+nx], s[j], syz[j/3]) :
            leq(s[i], s[i+1], syz[sayz[t]-nx+1],
        s[j], s[j+1], syz[j/3+nx]) )
        {
            sa[e] = i;
            if (++t == nxz)
            {
                for (e++; p < nx; p++, e++)
                sa[e] = sax[p];
            }
        }
        else
        {
            sa[e] = j;
            if (++p == nx) for (++e; t < nxz; ++t, ++e)
            sa[e] = geti(t, nx, sayz);
        }
    }
}
void makesa()
{
    memset(buf, 0, 4 * n * sizeof(int));
    memset(sa, 0, 4 * n * sizeof(int));
    for (int i=0; i<n; ++i) buf[i] = s[i];
    suffix(buf, sa, n, 255);
}

void getRank()
{
    for(int i = 1;i < n; ++ i)
        rank[sa[i]] = i;
}

void lcp()
{ // O(4 * N)
    int i, j, k;
    for (j = rank[height[i=k=0]=0]; i < n - 1; i++, k++)
        while (k >= 0 && s[i] != s[ sa[j-1] + k ])
            height[j] = (k--), j = rank[ sa[j] + 1 ];
}
int s2[N];
int main()
{
    while(scanf("%d", &n) && n)
    {
        for(int i = 0; i < n; i++)
            scanf("%d", &s2[i]);
        for(int i = 0; i < n - 1; i++)
            s[i] = s2[i] - s2[i + 1] + 100;
        s[n - 1] = '\0';
        makesa(); getRank(); lcp();
        int ans = 0, l = 4, r = n;
        while(l <= r)
        {
            int mid = (l + r) >> 1;
            int mmin = 0x7fffffff, mmax = -1, flag = 0;
            for(int i = 2; i < n; i++)
            {
                if (height[i] < mid)
                {
                    if (mmax != -1 && mmax - mmin >= mid){flag = true; break;}
                    mmin = 0x7fffffff, mmax = -1;
                    continue;
                }
                else
                {
                    mmin = min(mmin, sa[i - 1]); mmin = min(mmin, sa[i]);
                    mmax = max(mmax, sa[i - 1]); mmax = max(mmax, sa[i]);
                }
            }
            if (mmax != -1 && mmax - mmin >= mid)flag = true;
            if (flag) {l = mid + 1; ans = max(ans, mid + 1);}
            else r = mid - 1;
        }
        printf("%d\n", ans);
    }
    return 0;
}