UVA - 12206 Stammering Aliens (hash)

本文主要是介绍UVA - 12206 Stammering Aliens (hash)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

     这题其实很容易想到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;
}

这篇关于UVA - 12206 Stammering Aliens (hash)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---