题解 P3370 【【模板】字符串哈希】
前言： 哈希算法，即通过函数来将字符串转化为一个数值，这个数值就称之为哈希值。利用哈希算法可以实现字符串问题的快速查找与匹配。
字符串哈希
哈希值的计算
对于字符串
S=s_1s_2s_3\cdots s_m ，我们要计算其哈希值。为了便于计算，我们将每个字符对应到一个数上 设若函数f(x) ，一个字符x 有且仅有唯一的f(x) 与其对应 为何要定义这样的f(x) ? 原因：对于不同的题目，会有全为大（小）写字母或混杂数字，此时的ASCII 码是不连续的，我们就可以将计算范围缩小（当然，强制类型转换亦可）
例如下面的
int f(char ch)
{
if(isupper(ch)) return ch-'A'+1;
if(islower(ch)) return ch-'a'+27;
if(isdigit(ch)) return ch-'0'+53;
}现在我们定义这样一个函数：
b指base，即进制，h为模数
其本质就是
举个栗子：字符串
哈希匹配问题
现在有了这个函数，我们来考虑字符串的匹配问题
举个栗子：字符串
其中字符串
某一字符串的哈希值计算： 前面，我们定义
H(x) 为S 的哈希函数，其实其本质就是相当于一个前缀和，表示序号为1 到x 组成的字符串的哈希值 如字符串S=BCAB ，f(A)=1,f(B)=2,f(C)=3,base=3,h=47 则H(3)=(2\times3^2+3\times3^1+1\times3^0)\ \bmod\ 47 那么计算时我们就可以用秦九韶算法 当然，对于懒癌患者，我们不知道unsigned long long能自然溢出，即对2^{64} 取模，就省去了手动取模
以下为
h[0]=0;
for(register int i=1;i<=m;i++)
h[i]=(h[i-1]*b+f(s[i]))%mod;代码实现
一、子串查找（LOJ）：给定两个字符串，求子串在主串中的出现次数
#include<bits/stdc++.h>
using namespace std;
const int maxN=1000000;
typedef unsigned long long ull;
ull mul[maxN+1],h[maxN+1],b=53;
//mul:表示b的幂
//h:哈希函数
//b:base，进制
char s2[maxN+1],s1[maxN+1];
int n,m,ans=0;
ull f(char ch)
{
if(isupper(ch)) return ch-'A'+1;
if(islower(ch)) return ch-'a'+27;
}
int main()
{
mul[0]=1; scanf("%s%s",s1+1,s2+1);
for(register int i=1;i<maxN;i++)
mul[i]=mul[i-1]*b;
n=strlen(s2+1); m=strlen(s1+1);
h[0]=0;
for(register int i=1;i<=m;i++)
h[i]=h[i-1]*b+f(s1[i]);
ull s=0;
for(register int i=1;i<=n;i++)
s=s*b+f(s2[i]);
for(register int i=0;i<=m-n;i++)
if(s==h[i+n]-h[i]*mul[n]) ans++;
printf("%d",ans);
return 0;
}二、【模板】字符串哈希（洛谷）：判断相同字符串个数
#include<bits/stdc++.h>
using namespace std;
const int maxN=10000;
long long mod=1e9+7,x=89;
long long a[maxN+1];
char s[1600];
int n,tot=0;
int f(char ch)
{
if(isupper(ch)) return ch-'A'+1;
if(islower(ch)) return ch-'a'+27;
if(isdigit(ch)) return ch-'0'+53;
}
long long h(char s[])
{
int len=strlen(s); long long h=0;
for(register int i=0;i<len;i++)
h=(h*x+f(s[i]))%mod;
return h;
}
int main()
{
scanf("%d",&n);
for(register int i=1;i<=n;i++) {scanf("%s",s); a[i]=h(s);}
sort(a+1,a+n+1);
for(register int i=1;i<=n;i++)
if(a[i]!=a[i-1]) tot++;
printf("%d",tot);
return 0;
}存在的问题
回到先前的例子
字符串
S=BCAB ，f(A)=1,f(B)=2,f(C)=3,base=3,h=47 则H(S)=(2\times3^3+3\times3^2+1\times3^1+2\times3^0)\ \bmod\ 47=86\ \bmod\ 47=39
看上去并没有什么问题，但其实隐藏着巨大的隐患：
我们看字符串
此时我们的哈希值就出现了重复：