萌新求问关于base、mod、prime 必要性、如何取的原理
查看原帖
萌新求问关于base、mod、prime 必要性、如何取的原理
452688
cywuuuu楼主2021/2/7 20:43
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
//进制hash 
//FILE* fp = freopen("P3370_2.in","r",stdin);
int cmp (const void * a, const void * b)
{
   return ( *(int*)a - *(int*)b );
}
typedef unsigned long long ull;
ull mod = 1<<30;
ull base = 999979, prime = 1e9+7;
//定义一个大数(最好是质数)作为模数,这里用的是1<<30
//定义一个base进制,这里是233
/*
2. hash[i]=(hash[i-1]*p+idx(s[i]))%mod
p取一个6到8位的素数,mod取一个大素数,一般取1e9+7或1e9+9
安全指数:四星 (还可以)*/
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
ull hash[300000]={0}; 
char s[200000];
int main(int argc, char** argv) {
	ull hashnum=0;
	int n=0;
	scanf("%d",&n); 
	int cnt=0,much=0;
	while(scanf("%s",s)!=EOF)
	{
		hashnum = 0;
		int len = strlen(s);
		for(int i = 0 ;i < len ;i++)
		{
			hashnum = (hashnum*base + (ull)s[i])%mod+prime;
		}
		hash[cnt] = hashnum;
		cnt++;
	}
	qsort(hash,cnt,sizeof(ull),cmp);
	for(int i=0;i<cnt-1;i++)
	{
		if(hash[i]!=hash[i+1])much++;
	}
	printf("%d",much+1);
//	fclose(fp);
	return 0;
}

怎么说呢,小白试了很多次,终于AC,但是对于这里面取值的讲究,为什么这么取还不是很明白。求巨佬解答求求!

2021/2/7 20:43
加载中...