codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include<iostream> #include<cstdio> #include<cstdlib> #include<ctime> #include<utility> #include<algorithm> #include<vector> #include<queue> #include<set> #include<map> #include<cmath> #include<cstring> #include<cctype> #include<string> #include<string.h> #include<list> #include<strstream> using namespace std; struct node { int now,next; }; int n; int x[20005]; int rank[20005],sa[20005]; int pos[20005],val[2][20005],c[20005]; node d[20005]; int height[20005],h[20005]; int min(int x,int y) { return x<y ? x : y; } int max(int x,int y) { return x>y ? x : y; } void add_value(int u,int v,int i) { d[i].next=c[u];c[u]=i; d[i].now=v; } void radix_sort(int l,int r) { for(int k=1;k>=0;k--) { memset(c,0,sizeof(c)); for(int i=r;i>=l;i--) { add_value(val[k][pos[i]],pos[i],i); } int t=0; for(int i=0;i<=20000;i++) { for(int j=c[i];j;j=d[j].next) pos[++t]=d[j].now; } } int t=0; for(int i=1;i<=n;i++) { if(val[0][pos[i]]!=val[0][pos[i-1]] || val[1][pos[i]]!=val[1][pos[i-1]]) t++; rank[pos[i]]=t; } } void get_suffix_array() { int t=1; while(t/2<=n) //****** { for(int i=1;i<=n;i++) { val[0][i]=rank[i]; if(i+t/2<=n) val[1][i]=rank[i+t/2]; else val[1][i]=0; pos[i]=i; } radix_sort(1,n); t*=2; } for(int i=1;i<=n;i++) sa[rank[i]]=i; } //------------------------------------------------------------------------------- void get_common_prefix() { memset(h,0,sizeof(h)); for(int i=1;i<=n;i++) { if(rank[i]==1) h[i]=0; else { int now=0; if(i>1 && h[i-1]>1) now=h[i-1]-1; while(now+i<=n && now+sa[rank[i]-1]<=n && x[now+i]==x[now+sa[rank[i]-1]]) now++; h[i]=now; } } for(int i=1;i<=n;i++) height[rank[i]]=h[i]; } //------------------------------------------------------------------------------- bool exist(int len) { int minn=n+1,maxx=0; for(int i=1;i<=n;i++) { if(height[i]<len) { if(maxx-minn>=len) return true; minn=maxx=sa[i]; } else { minn=min(minn,sa[i]); maxx=max(maxx,sa[i]); } } if(maxx-minn>=len) return true; return false; } int binary_search(int ln,int rn) { while(rn-ln>1) { int mid=(ln+rn)>>1; if(exist(mid)) ln=mid; else rn=mid; } return ln; } int main() { scanf("%d",&n); while(n!=0) { for(int i=1;i<=n;i++) scanf("%d",&x[i]); for(int i=1;i<=n-1;i++) x[i]=rank[i]=x[i+1]-x[i]+88; n--; get_suffix_array(); get_common_prefix(); int ans=binary_search(0,n)+1; printf("%d\n",ans<5 ? 0 : ans); scanf("%d",&n); } return 0; }
Private
[
?
]
Run code
Submit