題意：

給出n和k，n代表數字的個數，k代表你要求至少出現k次的，下面是n個數字，求出在其中至少出現k次的可重疊的子串的長度。

思路：

類似于1743但又不同于1743，思路大體上差不多，二分答案+判定。

還是分組，然后看每組的個數是否大于k就ok了。

代碼：

#include<cstdio> #include<cstring> #include<iostream>#define maxn 20005int wa[maxn],wb[maxn],wv[maxn],ws[maxn]; int cmp(int *r,int a,int b,int l) {return r[a]==r[b]&&r[a+l]==r[b+l];} void da(int *r,int *sa,int n,int m) {int i,j,p,*x=wa,*y=wb,*t;for(i=0;i<m;i++) ws[i]=0;for(i=0;i<n;i++) ws[x[i]=r[i]]++;for(i=1;i<m;i++) ws[i]+=ws[i-1];for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;for(j=1,p=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<n;i++) wv[i]=x[y[i]];for(i=0;i<m;i++) ws[i]=0;for(i=0;i<n;i++) ws[wv[i]]++;for(i=1;i<m;i++) ws[i]+=ws[i-1];for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;}return; } int rank[maxn],height[maxn]; void calheight(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 n,int k,int mid) {int ans=1;//不能是0for(int i=1;i<=n;i++){if(height[i]>=mid){ans++;if(ans>=k)return 1;}elseans=1;}return 0; }int main() {//freopen("in.txt","r",stdin);int r[maxn],sa[maxn];int n,k;while(scanf("%d%d",&n,&k)!=EOF){for(int i=0;i<n;i++){scanf("%d",&r[i]);r[i]++;}r[n]=0;da(r,sa,n+1,200);calheight(r,sa,n);int min=1,max=n;while(min<=max){int mid=(min+max)/2;if(check(n,k,mid))min=mid+1;elsemax=mid-1;}printf("%d\n",max);}return 0; }

總結

以上是生活随笔為你收集整理的poj3261（求至少出现k次的可重叠的子串的长度）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。