这题其实很容易想到2分长度，关键是2分后，怎么判断出现最多次的串是否》=m次了。这里需要用到hash来处理。 对于一个字符串 H[i] =H[i+1]*131+s[i] ;其中 H[n]=0；那么对于一个长度为L的串 ，hanh[i,l]=H[i]-H[i+L]*x^L ; 这样记录每个字符串的hash值，，然后再处理起来就比较简单了。
VIEW CODE
#include<cstdio>#include<algorithm>#include<iostream>#include<cmath>#include<queue>#include<stack>#include<string>#include<cstring>#include<map>#include<vector>#include<set>#include<ctime>#include<stdlib.h>using namespace std;const int mmax= 1000010;const int mod=1000000007;const int inf=0x3fffffff;using namespace std;typedef long long LL;typedef unsigned long long ULL;ULL H[mmax];map<ULL,int>q;int m;char str[mmax];ULL Pow[mmax];void build_ha(){int n=strlen(str);H[n]=0;for(int i=n-1;i>=0;i–)H[i]=H[i+1]*131+str[i];}ULL Ha[mmax];bool ok(int k){int n=strlen(str);for(int i=0;i+k-1<n;i++){ULL tmp=H[i]-H[i+k]*Pow[k];Ha[i]=tmp;}sort(Ha,Ha+n-k+1);int cnt=0;for(int i=0;i<n-k+1;i++){if( i && Ha[i]==Ha[i-1])cnt++;else{if(cnt>=m)return 1;cnt=1;}}if(cnt>=m)return 1;return 0;}int main(){Pow[0]=1;for(int i=1;i<mmax;i++)Pow[i]=Pow[i-1]*131;while(cin>>m&&m){scanf("%s",str);int n=strlen(str);int l=1,r=n+1;build_ha();while(l<r){int mid=(l+r)>>1;if(ok(mid))l=mid+1;elser=mid;}int ans=r-1;if(!ans){puts("none");continue;}int e;q.clear();for(int i=0;i+ans-1<n;i++){ULL tmp=H[i]-H[i+ans]*Pow[ans];q[tmp]++;if(q[tmp]>=m)e=i;}printf("%d %d\n",ans,e);}return 0;}
愚者用肉体监视心灵，智者用心灵监视肉体
