[POJ 1200]Crazy Search

danihao123 posted @ 2016年9月25日 08:50 in 题解 with tags POJ Hash , 280 阅读
转载请注明出处:http://danihao123.is-programmer.com/

很容易想到哈希+set判重的方法,但好像会T吧……

那么就要直接开哈希表了,但是哈希函数会很大,怎么办呢?

我们看到还有一个NK啊……这样就有一个行之有效的方法了:将字符串里的字符映射到[tex][0,NK-1][/tex],然后就可以开哈希表了……

代码:

#include <cstdio>
#include <cstring>
const int maxn=16000005;
int length,k;
bool P[maxn];
unsigned int hash[maxn],x_pow[maxn];
unsigned int ns[maxn];
void InitHash(){
	register int i;
	for(i=length;i>=1;i--)
		hash[i]=ns[i]+hash[i+1]*k;
	x_pow[0]=1;
	for(i=1;i<=length;i++)
		x_pow[i]=x_pow[i-1]*k;
}
unsigned int Hash(int i,int L){
	return hash[i]-x_pow[L]*hash[i+L];
}
char s[maxn];
int a[128];
int main(){
	int n;
	register int i,j=0,ans=0;
	scanf("%d%d",&n,&k);
	scanf("%s",s);
	length=strlen(s);
	for(i=0;i<length;i++){
		if(!a[s[i]]){
			a[s[i]]=j++;
		}
		if(j==k)
			break;
	}
	for(i=1;i<=length;i++){
		ns[i]=a[s[i-1]];
	}
	InitHash();
	for(i=1;i<=(length-n+1);i++){
		j=Hash(i,n);
		if(!P[j]){
			P[j]=true;
			ans++;
		}
	}
	printf("%d\n",ans);
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter