后缀数组： 构建后缀数组，注意要在字符串莫末尾加上一个没出现过的字符。然后可以2分或者直接扫描，直接扫描需要用单调队列来维护
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= 40010;const int mod=1000000007;typedef long long LL;//typedef unsigned long long ULL;char s[mmax];int sa[mmax],t[mmax],t2[mmax],c[mmax],n;void build_sa(int m){int i,*x=t,*y=t2;for(i=0;i<m;i++) c[i]=0;for(i=0;i<n;i++) c[ x[i]=s[i]]++;for(i=1;i<m;i++) c[i]+=c[i-1];for(i=n-1;i>=0;i–) sa[–c[x[i]]]=i;for(int k=1;k<=n;k<<=1){int p=0;for(i=n-k;i<n;i++) y[p++]=i;for(i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;for(i=0;i<m;i++) c[i]=0;for(i=0;i<n;i++) c[x[y[i]]]++;for(i=1;i<m;i++) c[i]+=c[i-1];for(i=n-1;i>=0;i–) sa[–c[x[y[i]]]]=y[i];swap(x,y);p=1;x[sa[0]]=0;for(i=1;i<n;i++)x[sa[i]] = y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;if(p>=n) break;m=p;}}int rank[mmax],heigth[mmax];void getheigth(){for(int i=0;i<n;i++)rank[sa[i]]=i;int k=0;for(int i=0;i<n;i++){if(k) k–;if(rank[i]){int j=sa[rank[i]-1];while(s[i+k]==s[j+k]) k++;heigth[rank[i]]=k;}}}int len[mmax];int mark[mmax];int head,end,head1,end1;int main(){int m;while(scanf("%d",&m)&&m){head=end=0;head1=end1=0;scanf("%s",s);if(m==1){printf("%d %d\n",strlen(s),0);continue;}n=strlen(s);s[n++]='$';s[n]=0;build_sa(131);getheigth();for(int i=1;i<m;i++){while(end>head && heigth[len[end-1]]>= heigth[i])end–;len[end++]=i;while(end1>head1 && sa[mark[end1-1]] <sa[i] )end1–;mark[end1++]=i;}int ans=heigth[len[head]];int e=sa[mark[head1]];for(int i=m;i<n;i++){if(i-m+1==len[head])head++;while(end>head && heigth[len[end-1]]>= heigth[i])end–;len[end++]=i;if(i-m==mark[head1])head1++;while(end1>head1 && sa[mark[end1-1]] <sa[i] )end1–;mark[end1++]=i;if(heigth[len[head]]>ans){ans=heigth[len[head]];e=sa[mark[head1]];}else if(heigth[len[head]]==ans)e=max(e,sa[mark[head1]]);}if(ans==0){puts("none");continue;}printf("%d %d\n",ans,e);}return 0;}字符串hash ： 直接2分了 很好写的
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;}
，你在雨中行走，你从不打伞，你有自己的天空，它从不下雨。
