题目链接
题意： 给定一个字符串T，在T里面找出一个子串s使得子串s在T里面至少出现m次。输出最长字符串的长度和起始位置的最大值。（起始位置从0开始 ）如果不存在输出“none”。
分析： 因为 如果一个子串s出现的m次，那么s的子串出现的次数一定大于等于m次，故这个是单调的，所以我们可以用二分来枚举长度L 。
然后将所有长度为L的子串都Hash出来，如果Hash值相同，说明字符串相同。
详细的看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define ULL unsigned long longconst int N = 1e5+11;
const int M = 1e6+11;
const int mod = 1e9+7;
const int inf =0x3f3f3f3f;
const int seed = 233;ULL H[N],X[N],Hash[N];
int len,pos,Rank[N];
int m;void init(char *s){ // 这样处理之后，对于s的所有子串都可以在o(1)的时间内求出Hash值len=strlen(s);H[len]=0;for(int i=len-1;i>=0;i--) {H[i]=H[i+1]*seed+s[i]-'a';}X[0]=1;for(int i=1;i<=len;i++) {X[i]=X[i-1]*seed;}
}bool cmp(int a,int b){if(Hash[a]!=Hash[b])return Hash[a]<Hash[b];return a<b;
}bool Judge(int L){for(int i=0;i<len-L+1;i++){Hash[i]=H[i]-H[i+L]*X[L];Rank[i]=i;}sort(Rank,Rank+len-L+1,cmp); //将所有长度为L的子串 Hash sort一下int cnt=0; pos=-1;for(int i=0;i<len-L+1;i++){if(!i || Hash[Rank[i]]!=Hash[Rank[i-1]]) cnt=0;cnt++;if(cnt>=m) pos=max(pos,Rank[i]);}return pos>=0;
}
char str[N];
int main(){while(scanf("%d",&m)!=EOF &&m){scanf("%s",str);init(str);int ans=-1;int le=1,ri=len;while(le<=ri){ // 二分枚举 长度L int mid=(le+ri)>>1;if(Judge(mid)){// cout<<mid<<endl;ans=max(ans,mid);le=mid+1;}else ri=mid-1;}if(ans==-1) puts("none");else {Judge(ans);printf("%d %d\n",ans,pos);}}return 0;
}