poj1743

思路

不得不说，罗穗骞太厉害了
他写的论文比哪一篇博客都好
去看吧，也别看我的了
里面有这题目详解
论文

代码

// 不得不说，罗穗骞nb哇,%%%%%%%%%
/*
0 0 1 1 2 2 3 3 4

10
1 2 3 4 5 1 2 3 4 5 
差分 1 1 1 1 0 1 1 1 1
height 0 0 1 1 2 2 3 3 4
后缀子串
111101111
11101111
1101111
101111
01111
1111
111
11
1
排序子串
01111
1
101111
11
1101111
111
11101111
1111
111101111
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define ROF(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
const int maxn=1e5+7;
const int inf=0x3f3f3f3f;
int s[maxn];
int n,m,x[maxn],c[maxn],rk[maxn],sa[maxn];
int read() {
    int x=0,f=1;char s=getchar();
    for(;s<'0'||s>'9';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
void get_sa() {
    FOR(i,1,m) c[i]=0;
    FOR(i,1,n) ++c[rk[i]=s[i]];
    FOR(i,2,m) c[i]+=c[i-1];
    ROF(i,n,1) sa[c[rk[i]]--]=i;
    for(int k=1;k<=n;k<<=1) {
        int p=0;
        FOR(i,n-k+1,n) x[++p]=i;
        FOR(i,1,n) if(sa[i]>k) x[++p]=sa[i]-k;
        FOR(i,1,m) c[i]=0;
        FOR(i,1,n) ++c[rk[i]];
        FOR(i,2,m) c[i]+=c[i-1];
        ROF(i,n,1) sa[c[rk[x[i]]]--]=x[i],x[i]=0;
        swap(rk,x);
        rk[sa[1]]=1,p=1;
        FOR(i,2,n)
            rk[sa[i]]=(x[sa[i]]==x[sa[i-1]]&&x[sa[i]+k]==x[sa[i-1]+k]) ? p : ++p;
        if(p==n) break;
        m=p;
    }
}
int height[maxn];
void get_height() {
    FOR(i,1,n) rk[sa[i]]=i;
    int k=0;
    FOR(i,1,n) {
        k=k?k-1:0;
        while(s[i+k]==s[sa[rk[i]-1]+k])k++;
        height[rk[i]]=k;
    }
}
bool check(int x) {
    int mi=inf,ma=-inf;
    FOR(i,1,n) {
        if(height[i]>=x) {
            mi=min(mi,sa[i-1]);
            mi=min(mi,sa[i]);
            ma=max(ma,sa[i-1]);
            ma=max(ma,sa[i]);
            if(ma-mi>=x) return 1;
        } else mi=inf,ma=-inf;
    }
    return 0;
}
int main() {
    while(scanf("%d",&n)==1 && n) {
        FOR(i,1,n) s[i]=read();
        n--;
        FOR(i,1,n) s[i]=s[i+1]-s[i]+100;
        m=1888;
        get_sa();
        get_height();
        int l=0,r=n,ans=0;
        while(l<=r) {
            int mid=(l+r)>>1;
            if(check(mid)) ans=mid,l=mid+1;
            else r=mid-1;
        }
        ans++;
        if(ans>=5) cout<<ans<<"\n";
        else cout<<"0\n";
    }
    return 0;
}