题目描述：给一组数字串，求不可重叠的最长公共子串，如果长度大于5，输出长度，否则输出0。

注意：“公共子串”的定义为，两子串的对应位置的元素的差值相同即可。

如：1 2 3 和 6 7 8 即满足条件，他们对应位置的差值是2。


题解：我们如果有两个满足条件的子序列a[i],a[i+1],…a[i+k]和b[i],b[i+1],…b[i+k]，则有：b[i]-a[i]=b[i+1]-a[i+1]= …b[i+k]-a[i+k]。

我们将原数组的元素依次两两做差，差值加上88，形成一个新数组x[]，最后补一个0，使x数组有n个元素。

若有b[i+1]-b[i]=a[i+1]-a[i]，则有x[j]=x[k]（j和k分别对应b[i+1]和a[i+1]在原数组中的位置）。移项后，b[i+1]-a[i+1]=b[i]-a[i]。

若有b[i+2]-b[i+1]=a[i+2]-a[i+1],则有x[j+1]=x[k+1]。移项后，b[i+2]-a[i+2]=b[i+1]-a[i+1]。

若有b[i+3]-b[i+2]=a[i+3]-a[i+2],则有x[j+2]=x[k+2]。移项后，b[i+3]-a[i+3]=b[i+2]-a[i+2]。

......

发现若x数组中有长度为m的公共子串，则说明原数组中有长度为m+1的符合条件的子串。

接下来用后缀数组+二分解决即可。

先二分答案，把题目变成判定性问题：判断是否存在两个长度为 k 的子串是相同的，且不重叠。解决这个问题的关键还是利用height 数组。把排序后的后缀分成若干组，其中每组的后缀之间的 height 值都不小于 k。例如，字符串为“aabaaaab”，当 k=2 时，后缀分成了 4 组


容易看出，有希望成为最长公共前缀不小于 k 的两个后缀一定在同一组。然后对于每组后缀，只须判断每个后缀的 sa 值的最大值和最小值之差是否不小于k。如果有一组满足，则说明存在，否则不存在。


代码：

#include<cstdio>
#include<algorithm>
#define N 20010
#define LL long long
using namespace std;

int s[N];
int sa[N],t[N],t2[N],c[N],n,rak[N],height[N];

void build_sa(int m,int *s)
{
    int i,*x=t,*y=t2;
    for (i=0;i<m;i++)c[i]=0;
    for (i=0;i<n;i++)c[x[i]=s[i]]++;
    for (i=1;i<m;i++)c[i]+=c[i-1];
    for (i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
    for (int k=1;k<=n;k<<=1)
    {
        int p=0;
        for (i=n-k;i<n;i++)y[p++]=i;
        for (i=0;i<n;i++)if (sa[i]>=k)y[p++]=sa[i]-k;
        for (i=0;i<m;i++)c[i]=0;
        for (i=0;i<n;i++)c[x[y[i]]]++;
        for (i=0;i<m;i++)c[i]+=c[i-1];
        for (i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
        swap(x,y);
        p=1; x[sa[0]]=0;
        for (i=1;i<n;i++)
            x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
        if (p>=n) break;
        m=p;
    }
}

void getheight()
{
    int i,j,k=0;
    for (i=0;i<n;i++)rak[sa[i]]=i;
    for (i=0;i<n;i++)
    {
        if (k)k--;
        if (!rak[i])continue;
        j=sa[rak[i]-1];
        while (s[i+k]==s[j+k])k++;
        height[rak[i]]=k;
    }
}

bool check(int k)
{
    int x,y;
    for (int i=1;i<n;i++)
    {
        if (height[i]<k)
        {
            x=0;y=1000000;
        }else
        {
            x=max(x,sa[i]);
            y=min(y,sa[i]);
            x=max(x,sa[i-1]);
            y=min(y,sa[i-1]);
            if (x-y>=k)return true;
        }
    }
    return false;
}

int main()
{

    while (~scanf("%d",&n) && n)
    {
        for (int i=0;i<n;i++) scanf("%d",&s[i]);
        for (int i=0;i<n-1;i++) s[i]=s[i+1]-s[i]+88; s[n-1]=0;
        build_sa(200,s);
        getheight();
        int l=0,r=n;
        while (r-l>1)
        {
            int t=(l+r)>>1;
            bool f=check(t);
            if (f) l=t;else r=t;
        }
        int ans;
        if (check(r)) ans=r;else ans=l;
        if (ans>=4)printf("%d\n",ans+1);else puts("0");
    }
    return 0;
}