学步园

题目地址：http://poj.org/problem?id=1743

题目意思：

给你n个音符，每个音符到另外一个音符，会有一个转换值，即差值，形成一个串。

让你找出里面最长的重复串（至少重复2次），且不相互覆盖

要求，如果组成这些串的音符要>=5，即音乐差值组成的串要大于等于4

否则输出0

解题思路：

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

容易看出，有希望成为最长公共前缀不小于k 的两个后缀一定在同一组。然
后对于每组后缀，只须判断每个后缀的sa 值的最大值和最小值之差是否不小于
k。如果有一组满足，则说明存在，否则不存在。整个做法的时间复杂度为
O(nlogn)。本题中利用height 值对后缀进行分组的方法很常用，请读者认真体
会。

这是看的罗的论文的思路，但是有一个问题，罗是把r[n-1]作为额外字符的，但是他的模板给的不符

所以如果直接抄他的模板，要根据自己的来，这也是为什么要理解的原因，下面上代码：

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

const int maxn = 20000+10;

int str[maxn];

int wa[maxn],wb[maxn],wv[maxn];
int c[maxn];
int cmp(int *r,int a,int b,int l)
{
    return r[a]==r[b] && r[a+l]==r[b+l];
}

void cal_the_houzhui(int *r,int *sa,int n,int m)
{
    int i,j,p;
    int *x=wa,*y=wb;

    //先直接对每个后缀的第一个字符进行基数排序
    for(i=0;i<m;i++)
        c[i]=0;

    for(i=0;i<n;i++)
        c[x[i]=r[i]]++;
    for(i=1;i<m;i++)
        c[i]+=c[i-1];
    for(i=n-1;i>=0;i--)
        sa[--c[x[i]]]=i;

    //然后进行log级的基数排序，使得sa数组稳定
    p=1;
    for(j=1;p<n;j*=2,m=p)
    {
        //对第二维进行基数排序
        //可以直接利用sa数组进行排序
        //y[p]表示的在二维排序中，第P小的第一位在什么位置
        for(p=0,i=n-j;i<n;i++)
            y[p++]=i;//这里从n-j~n-1的是不可能有第二维的，因为第二维已经超出了n-1
                        //所以在第二维的排序中，他们是最小的，当然就是排在最前面的
        for(i=0;i<n;i++)
            if(sa[i]>=j)
                y[p++]=sa[i]-j;
        for(i=0;i<n;i++)//根据y数组来重新定义wv
            wv[i]=x[y[i]];

        for(i=0;i<m;i++)
            c[i]=0;
        for(i=0;i<n;i++)
            c[wv[i]]++;
        for(i=1;i<m;i++)
            c[i]+=c[i-1];
        for(i=n-1;i>=0;i--)
            sa[--c[wv[i]]] = y[i];
        swap(x,y);
        p=1;
        x[sa[0]] = 0;
        for(i=1;i<n;i++)
            x[sa[i]] = cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    }

}

int rank[maxn],height[maxn];

void cal_the_height(int *r,int *sa,int n)
{
    int i,j,k=0;
    //通过sa求出rank
    for(i=0;i<n;i++)
        rank[sa[i]]=i;
    for(i=0;i<n;height[rank[i++]]=k)
    {
        for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];)
            k++;
    }
}

int n;
int _sa[maxn];

bool judge(int mid)
{
    int _min=_sa[0];
    int _max=_sa[0];
    for(int i=1;i<n;i++)
    {
        if(height[i]>=mid)
        {
            _min=min(_min,_sa[i]);
            _max=max(_max,_sa[i]);
            if(_max-_min>=mid)
            {
                return true;
            }

        }
        else//如果中间发生断层，那就要另分一组了
            _min=_max=_sa[i];
    }
    return false;
}

void solve()
{
    cal_the_houzhui(str,_sa,n,256);
    cal_the_height(str,_sa,n);
    int low=1,high=n;
    int ans=-1;
    while(low<=high)
    {
        int mid=(low+high)>>1;
        if(judge(mid))
        {
            ans=mid;
            low=mid+1;
        }
        else
            high=mid-1;
    }
    if(ans>=4)//为什么是4，因为这是4个差，就是5个数
        printf("%d\n",ans+1);
    else
        puts("0");
}

int main()
{

    while(~scanf("%d",&n) && n)
    {
        int b,a;
        scanf("%d",&b);
        if(n==1)
        {
            printf("0\n");
            continue;
        }
        for(int i=0;i<n-1;i++)
        {
            scanf("%d",&a);
            str[i]=a-b+100;
            b=a;
        }
        str[n-1]=0;
        solve();
    }
    return 0;
}