这是一道很经典的题目了。。题目在：http://acm.pku.edu.cn/JudgeOnline/problem?id=1743
USACO上面的那次我是用DP过的，现在不能DP了。我学了一下SA。过掉了。不过又想到了一个用Hash的做法比较NB。。
首先把原系列换成差系列。。
方法还是二分，因为长度为l的重复字串存在那么l-1的肯定也存在，所以问题变成判断所有长度为l的字串中有没有相同且不相交的，这可以用Hash来解决，算出每个字串的Hash值然后用一个Hash表来保存，有点类似Rabin-Karp算法。。然后二分就OK了。。为了调试我还去USACO了一下。。好久没去了。有点怀念饿。。
Code：

/* PROG: theme LANG: C++ ID: Tom Chen*/#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstdlib>#include<cstring>#include<string>#include<vector>#include<set>#include<queue>#include<map>#define rep(i,n) for(int i=0;i<n;i++)#define For(i,a,b) for(int i=a;i<=b;i++)#define tr(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)#define all(x) x.begin(),x.end()#define pb push_backusing namespace std;const int inf=~0U>>1;typedef unsigned int uint;typedef vector<int> vi;typedef vector<vi> vvi;typedef pair<int,int> ii;const int maxn=20000,seed[]={131,1331,10007,133331},size=17771;int A[maxn],n,Len;struct Hash{ struct node { node*next; uint h[4]; int Max,Min; void Renew(int x) { Max=max(Max,x); Min=min(Min,x); } bool Legal() { return Max-Min>Len; } bool equals(uint _h[4])const { for(int i=0;i<4;i++) if(h[i]!=_h[i])return false; return true; } }Data[maxn],*Now,*H[size]; void Clear() { Now=Data; rep(i,size) H[i]=0; } node* new_node(uint h[4],int start,node*next) { memcpy(Now->h,h,sizeof(Now->h)); Now->Max=Now->Min=start; Now->next=next; return Now++; } bool Insert(uint h[4],int start) { int t=h[0]%size; for(node*i=H[t];i;i=i->next) if(i->equals(h)) { i->Renew(start); return i->Legal(); } H[t]=new_node(h,start,H[t]); return false; }}H;bool Check(int l){ H.Clear(); Len=l;uint e[4]={1,1,1,1}; rep(i,4)rep(j,l-1)e[i]*=seed[i]; uint h[4]={0}; rep(i,l)rep(j,4) h[j]*=seed[j],h[j]+=A[i]; H.Insert(h,0); for(int i=1;i+l<=n;i++) { rep(j,4) { h[j]-=A[i-1]*e[j]; h[j]*=seed[j]; h[j]+=A[i+l-1]; } if(H.Insert(h,i)) return true; } return false;}bool Init(){ cin>>n;if(!n)return false;rep(i,n)scanf("%d",A+i); rep(i,n-1) A[i]=A[i+1]-A[i]+90; –n; return true;}void Work(){ int l=0,r=n/2+2; while(l+1<r) { int m=(l+r)/2; if(Check(m))l=m; else r=m; } ++l; if(l<5)cout<<0<<endl; else cout<<l<<endl;}bool Solve(){ if(!Init())return false; Work(); return true;}int main(){ //freopen("in","r",stdin); //freopen("theme.in","r",stdin); //freopen("theme.out","w",stdout); while(Solve());}