题目思路：后缀数组，求可重叠的重复k次子串。
[cpp] #include #include #include #include #include #include #include #include #include //#include #include using namespace std; #define inf 0x3f3f3f3f #define M 1100000 int max(int a,int b) { return a>b a:b; } int min(int a,int b) { return a } struct node { int v,id; bool operator<(const node a)const { return v } }a[M]; int r[M],rank[M],sa[M],height[M]; int ws[M],wv[M],wa[M],wb[M]; bool cmp(int *r,int a,int b,int l) { return r[a]==r[b]&&r[a+l]==r[b+l]; } void da(int n,int m) { int i,j,p; int *x=wa,*y=wb; for(i=0;i { a[i].v=r[i]; a[i].id=i; } sort(a,a+n); p=1; x[a[0].id]=0; for(i=1;i { if(a[i].v==a[i-1].v) x[a[i].id]=p-1; else x[a[i].id]=p++; } m=p; for(i=0;i for(i=0;i for(i=1;i for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i; for(j=1,p=1;p { p=0; for(i=n-j;i for(i=0;i=j) y[p++]=sa[i]-j; for(i=0;i for(i=0;i for(i=0;i for(i=1;i for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i]; p=1; swap(x,y); x[sa[0]]=0; for(i=1;i { if(cmp(y,sa[i],sa[i-1],j)) x[sa[i]]=p-1; else x[sa[i]]=p++; } } } void calheight(int n) { int i,j,k; for(i=1;i<=n;i++) rank[sa[i]]=i; k=0; for(i=0;i { int tmp=sa[rank[i]-1]; for(j=k;r[i+k]==r[tmp+k];k++); height[rank[i]]=k; k --k:0; } } int check(int n,int len,int k) { int num=0,i; for(i=2;i<=n;i++) { if(height[i] num=0; else { num++; if(num>=k-1) return 1; } } return 0; } int main() { int i,n,k,left,right,mid; while(scanf("%d%d",&n,&k)!=EOF) { for(i=0;i r[n]=0; da(n+1,1000100); calheight(n); left=2;right=n; while(left<=right) { mid=(left+right)>>1; if(check(n,mid,k)) left=mid+1; else right=mid-1; } printf("%d\n",right); } }