本文主要是介绍poj 3882（Stammering Aliens） 后缀数组 或者 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= 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;
}这篇关于poj 3882（Stammering Aliens） 后缀数组 或者 hash的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
