2、Stammering Aliens
（aliens.cpp）
有一个口吃的外星人，说的话里包含很多重复的字符串，比如babab包含两个bab。给定这个外星人说的一句话，找出至少出现m次的最长字符串。
输入格式：
输入包含多组数据。每组数据第一行为整数m，第二行为一个仅包含小写字母的字符串，长度在m~40000之间。输出结束标志为m=0。
输出格式：
对于每组数据，如果不存在，则输出“none”，否则输出两个整数，即最长字符串的长度及其起始位置的最大值(最后一个满足要求的串的起始位置)。
Sample Input
3
baaaababababbababbab
11
baaaababababbababbab
3
cccccc
0
Sample Output
5 12
none
4 2
字符串hash加速，
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
using namespace std;
const int maxlen=4e4+5;
const int N=10000007;
int m,first[N+5],next[maxlen],cnt[maxlen],ans,L;
char ch[maxlen];
inline bool same(int i,int j,int len)
{
for(register int k=0;k<len;++k){
if(ch[i+k]!=ch[j+k])return 0;
}
return 1;
}
inline int hash(int l,int r){//铏氭寚
int ans=0;
for(register int i=l;i<r;i++){
ans=(ans*31+ch[i]-'a'+1)%N;
}
return ans;
}
inline bool judge(int len)
{
memset(first,0,sizeof(first));
memset(next,0,sizeof(next));
memset(cnt,0,sizeof(cnt));
bool back=0;
ans=0;
int end=L-len+1;//铏氭寚
for(register int i=1;i<=end;++i){
int key=hash(i,i+len);
bool fd=1;
for(register int j=first[key];j;j=next[j]){
if( same( i , j , len ) ){
fd=0;
cnt[j]++;
}
if(cnt[j]>=m){
if(ans<i)ans=i;
back=1;
}
}
if(fd){
next[i]=first[key];
first[key]=i;
cnt[i]++;
if(cnt[i]>=m){
if(ans<i)ans=i;
back=1;
}
}
}
return back;
}
int main()
{
freopen("aliens.in","r",stdin);
freopen("aliens.out","w",stdout);
while(scanf("%d",&m)==1){
if(!m)break;
scanf("%s",ch+1);
L=strlen(ch+1);
if( !judge(1) ){
printf("none\n");
continue;
}
int left=0,right=L+1;
int mid=(left+right)>>1;
while(left<right-1){
//printf("l=%d r=%d\n",left,right);
//printf("%d ",judge(mid));
if(judge(mid))left=mid;
else right=mid;
mid=(right+left)>>1;
}
if(judge(right))printf("%d %d\n",right,ans-1);
else if(judge(left))printf("%d %d\n",left,ans-1);
else printf("none\n");
}
return 0;
}
