poj1743

题解：

二分枚举子串长度，判断解是否成立

把互相之间LCP大于等于长度的分为一组

这通过个扫一遍height即可

因为后缀是有序的

相邻的后缀间的LCP必定的极大的

接下来就找到每个组里后缀sa值最大和最小的

如果差值大于（等于）k就成立

因为这样小下标的后缀沿着LCP下去走k步才不会盖到大下标的后缀。

代码：

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
const int N=20005;
using namespace std;
int n,p,q,k,a[N],v[N],h[N],sa[2][N],rk[2][N];
void calsa(int sa[N],int rk[N],int SA[N],int RK[N])
{
    for (int i=1;i<=n;i++)v[rk[sa[i]]]=i;
    for (int i=n;i;i--)
     if (sa[i]>k)SA[v[rk[sa[i]-k]]--]=sa[i]-k;
    for (int i=n-k+1;i<=n;i++)SA[v[rk[i]]--]=i;
    for (int i=1;i<=n;i++)
     RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i-1]]!=rk[SA[i]]||rk[SA[i]+k]!=rk[SA[i-1]+k]);
}
void getsa()
{
    memset(v,0,sizeof(v));
    p=0,q=1;
    for (int i=1;i<=n;i++)v[a[i]]++;
    for (int i=1;i<=200;i++)v[i]+=v[i-1];
    for (int i=1;i<=n;i++)sa[p][v[a[i]]--]=i;
    for (int i=1;i<=n;i++)
     rk[p][sa[p][i]]=rk[p][sa[p][i-1]]+(a[sa[p][i-1]]!=a[sa[p][i]]);
    for (k=1;k<n;k<<=1,swap(p,q))calsa(sa[p],rk[p],sa[q],rk[q]);
}
void geth()
{
    k=0;
    for (int i=1;i<=n;i++)
     if (rk[p][i]==1)h[rk[p][i]]=0;
     else 
      {
        int j=sa[p][rk[p][i]-1];
        while (a[i+k]==a[j+k])k++;
        h[rk[p][i]]=k;
        if (k>0)k--;
      }
}
int jud(int x)
{
    int mn=sa[p][1],mx=sa[p][1];
    for (int i=2;i<=n;i++)
     if (h[i]<x)mn=mx=sa[p][i];
     else 
      {
        mn=min(mn,sa[p][i]);
        mx=max(mx,sa[p][i]);
        if (mx-mn>=x)return 1;
      }
    return 0;
}
void solve()
{
    int l=0,r=n/2,ans;
    while (l<=r)
     {
        int mid=(l+r)>>1;
        if (jud(mid))ans=mid,l=mid+1;
        else r=mid-1;
     }
    if (ans<4)puts("0");
    else printf("%d
",ans+1);
}
int main()
{
    while (~scanf("%d",&n),n)
     {
        for (int i=1;i<=n;i++)scanf("%d",&a[i]);
        n--;
        for (int i=1;i<=n;i++)a[i]=a[i+1]-a[i]+100;
        getsa();
        geth();
        solve();
     }
    return 0;
}