题意:给你一串数,让你求不可重叠的最长重复子串。注意,这里只要差值序列相同即视作重复序列。当最长序列长度小于5时输出0
思路:后缀数组求不可重叠的最长重复子串。二分答案,把题目变成判定性问题:判断是否存在两个长度为k 的子串是相同的,且不重叠。解决这个问题的关键是利用height 数组。把排序后的后缀分成若干组,其中每组的后缀之间的height 值都不小于k。有希望成为最长公共前缀不小于k 的两个后缀一定在同一组。然后对于每组后缀,只须判断每个后缀的sa 值的最大值和最小值之差是否不小于k。如果有一组满足,则说明存在,否则不存在。整个做法的时间复杂度为O(nlogn)。
注意,这里是先求差值序列。那么对于差值序列,就不能判断不小于k,而是应该为大于k。
例如,对于1 1 1 1 1 1 1 1 1(9个)这个序列,得出的差值序列为1 1 1 1 1 1 1 1(8个)。若判定为>=k,k=4是可以通过的,而这样实际得出的原序列会有重叠。
#include<iostream> #include<cstdio> using namespace std; const int maxn=20010; const int INF=0x3f3f3f3f; int w[maxn],wa[maxn],wb[maxn],wv[maxn],r[maxn],sa[maxn],rank[maxn],height[maxn],n; int cmp(int *r,int a,int b,int l) { return r[a]==r[b] && r[a+l]==r[b+l]; } void make_sa(int *r,int *sa,int n,int m) { int i,j,p; int *x=wa,*y=wb,*t; for (i=0;i<m;i++) w[i]=0; for (i=0;i<n;i++) w[x[i]=r[i]]++; for (i=1;i<m;i++) w[i]+=w[i-1]; for (i=n-1;i>=0;i--) sa[--w[x[i]]]=i; for (p=1,j=1;p<n;j*=2,m=p) { for (p=0,i=n-j;i<n;i++) y[p++]=i; for (i=0;i<n;i++) if (sa[i]>=j) y[p++]=sa[i]-j; for (i=0;i<m;i++) w[i]=0; for (i=0;i<n;i++) w[wv[i]=x[y[i]]]++; for (i=1;i<m;i++) w[i]+=w[i-1]; for (i=n-1;i>=0;i--) sa[--w[wv[i]]]=y[i]; for (t=x,x=y,y=t,p=1,i=1,x[sa[0]]=0;i<n;i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; } } void make_height(int *r,int *sa,int n) { int i,j,k=0; for (i=1;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++); return; } int check(int k) { int maxx=0,minn=INF; for(int i=1;i<=n;i++) { if(height[i]<k) maxx=minn=sa[i]; else { if(sa[i]>maxx) maxx=sa[i]; if(sa[i]<minn) minn=sa[i]; if(maxx-minn>k) return 1; } } return 0; } int work(int l,int r) { int mid,ans; while(l<=r) { mid=(l+r)>>1; if(check(mid)) { l=mid+1; ans=mid; } else r=mid-1; } return ans; } int main() { scanf("%d",&n); while(n!=0) { for(int i=0;i<n;i++) scanf("%d",&r[i]); for(int i=0;i<n-1;i++) r[i]=r[i+1]-r[i]+100; r[--n]=0; make_sa(r,sa,n+1,300); make_height(r,sa,n); int ans=work(0,n)+1; if(ans<5) ans=0; printf("%d\n",ans); scanf("%d",&n); } return 0; }