学习笔记：哈希字符串

第一种方法：自然溢出法。

实例代码：这里prime=233

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull h[15],p[15];
char s[15];
int main(){
	scanf("%s",s+1);
	int len=strlen(s+1);
	p[0]=1;
	for(int i=1;i<=len;i++)
		p[i]=p[i-1]*233,h[i]=h[i-1]*233+s[i];
	for(int i=1;i<=len;i++)
		printf("h[%d]=%ull\n",i,h[i]);
	int l,r;
	while(~scanf("%d%d",&l,&r)){
		printf("Hash_sub_string: from %d to %d:\n",l,r);
		ull hash=h[r]-h[l-1]*p[r-l+1];
		printf("%ull\n",hash);
	}
	return 0;	
}

输出结果：