Description 给出一个字符串，求这个字符串中重复次数不少于m次的最长字串长度以及这个子串在原串中最后一次出现的位置 Input 多组用例，每组用例第一行为一整数m，第二行为一长度不超过40000的字符串，以m=0结束输入 Output 输出两个整数，第一个整数为在这个字符串中重复次数不少于m次的最长子串的长度，第二个整数是这个子串在原串中最后一次出现的位置，如果不存在这样的子串则输出none Sample Input 3 baaaababababbababbab 11 baaaababababbababbab 3 cccccc 0 Sample Output 5 12 none 4 2 正解思路： 对原串做完后缀数组后二分最大长度，对于每个二分值k，对height数组分组，如果某组中后缀数量大于等于m则找到这个组中sa[i]的最大值来更新答案值 代码：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define MAXN 44444 int 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]; } int sa[MAXN],rnk[MAXN],height[MAXN]; void SA(int *r,int n,int m){ int *x=wa,*y=wb; for(int i=0; i<m; ++i) ws[i]=0; for(int i=0; i<n; ++i) ++ws[x[i]=r[i]]; for(int i=1; i<m; ++i) ws[i]+=ws[i-1]; for(int i=n-1; i>=0; --i) sa[--ws[x[i]]]=i; int p=1; for(int j=1; p<n; j<<=1,m=p){ p=0; for(int i=n-j; i<n; ++i) y[p++]=i; for(int i=0; i<n; ++i) if(sa[i]>=j) y[p++]=sa[i]-j; for(int i=0; i<n; ++i) wv[i]=x[y[i]]; for(int i=0; i<m; ++i) ws[i]=0; for(int i=0; i<n; ++i) ++ws[wv[i]]; for(int i=1; i<m; ++i) ws[i]+=ws[i-1]; for(int i=n-1; i>=0; --i) sa[--ws[wv[i]]]=y[i]; swap(x,y); x[sa[0]]=0; p=1; for(int i=1; i<n; ++i) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; } for(int i=1; i<n; ++i) rnk[sa[i]]=i; int k=0; for(int i=0; i<n-1; height[rnk[i++]]=k){ if(k) --k; for(int j=sa[rnk[i]-1]; r[i+k]==r[j+k]; ++k); } } char str[MAXN]; int n,m,a[MAXN]; bool isOK(int len){ int left=-1,right,mx=0; for(int i=2; i<=n; ++i){ if(height[i]>=len){ if(left==-1) left=i-1; right=i; }else{ left=-1; } if(left!=-1) mx=max(mx,right-left+1); } return mx>=m; } int getRightMost(int len){ int left=-1,right,mx=0,tmp=0; for(int i=2; i<=n; ++i){ if(height[i]>=len){ if(left==-1) left=i-1; right=i; tmp=max(tmp,max(sa[i-1],sa[i])); }else{ left=-1; tmp=0; } if(left!=-1){ if(right-left+1>=m) mx=max(mx,tmp); } } return mx; } int main(){ while(scanf("%d",&m)==1 && m){ scanf("%s",str); n=strlen(str); if(m==1){ printf("%d %d\n",n,0); continue; } for(int i=0; i<n; ++i){ a[i]=str[i]-'a'+1; } a[n]=0; SA(a,n+1,28); int l=0,r=MAXN; while(l<r){ int mid=l+r+1>>1; if(isOK(mid)) l=mid; else r=mid-1; } if(l==0){ puts("none"); continue; } printf("%d %d\n",l,getRightMost(l)); } return 0; }