哈希是一种映射，将字符串映射到整数上。
由于得到的哈希值都很大，不能直接映射到一个巨大的空间上，所以一般都需要限制空间。限制空间的方法是取模，把得到的哈希值对一个设定的空间大小 $M$ 取模，得到的结果作为索引地址。当然，这样可能会产生哈希冲突。
可以采取一种“隐性取余”的简化方法。取空间大小为 $M= 2^{64}$ ，而 $64$ 是 unsigned long long 型的长度，一个 unsigned long long 型的哈希值 $H$ ，当 $H>M$ 时会自动溢出，等价于自动对 $M$ 取模，这样能够避免低效的取模运算。
BKDRHash
最常用的就是进制哈希 $\mathrm{BKDRHash}$ 。
其计算步骤非常简单。设定一个进制 $P$ ，需要计算一个字符串的哈希值时，把每个字符看作将每个进制位上的一个数字，这个串转换为一个基于进制 $P$ 的数，最后对 $M$ 取模，就得到哦啊了这个字符串的哈希值。
例如计算只由小写字母构成的字符串的哈希值时，以字符串 abc 为例，令进制 $P=131$ ，那么该字符串的哈希值有以下两种计算方法：
- 把每个字符看做一个数字，即 $a=1,b=2,c=3,\dots,z=26$ ，然后当成 $P$ 进制来算，得到其哈希值为 $1\times 131^2+2\times 131^1+3\times 131^0=17426$ 。
- 直接把每个字符的 ACSII 码看作代表它的数字也可以，计算得到其哈希值为 $97\times 131^2+98\times 131^1+99\times 131^0=1677554$ 。
进制 $P$ 常用的值有 $31,131,1313,13131,131313$ 等，用这些树值能够有效避免碰撞。
例题 洛谷P3370 【模板】字符串哈希
如题，给定 $N$ 个字符串（第 $i$ 个字符串长度为 $M_i$，字符串内包含数字、大小写字母，大小写敏感），请求出 $N$ 个字符串中共有多少个不同的字符串。
思路
直接根据上面的运算来写即可。
这里我采取了第二种计算方法。
代码
#include<bits/stdc++.h>
#define N 10010
#define ull unsigned long long
using namespace std;
ull h[N];
char s[N];
ull BKDRHash(char *s) { //计算哈希值
ull P=131,H=0;
while(*s) H=H*P+(*s++);
return H;
}
int main() {
int n;
scanf("%d",&n);
for(int i=0;i<n;i++) {
scanf("%s",s);
h[i]=BKDRHash(s);
}
int ans=0;
sort(h,h+n);
for(int i=0;i<n;i++) if(h[i]!=h[i+1]) ans++;
printf("%d\n",ans);
system("pause");
return 0;
}进制哈希的应用
进制哈希的特征：可以按照进制做算术运算。
利用这一特征可以快速计算字符串 S 的所有前缀的哈希值。
例如字符串 $\mathrm{abc}$ ，其前缀有 $\{\mathrm{a},\mathrm{ab},\mathrm{abc} \}$，哈希值计算如下：
- 计算前缀 $\mathrm{a}$ 的哈希值，得到 $H(a)$ ，时间复杂度 $O(1)$ 。
- 计算前缀 $\mathrm{ab}$ 的哈希值。 $H(ab)=H(a)\times P+H(b)$ ，时间复杂度 $O(1)$ 。
- 计算前缀 $\mathrm{abc}$ 的哈希值。 $H(abc)=H(ab)\times P+H(c)$ ，时间复杂度 $O(1)$ 。
所以 $O(|S|)$ 便可以预处理字符串 $\mathrm{S}$ 的所有前缀的哈希值。
计算出所有前缀的哈希值后，能以 $O(1)$ 的复杂度查询它的任意子串的哈希值。
具体实现方式如下：
ull get_hash(ull L,ull R) {return H[R]-H[L-1]*P[R-L+1];}其中 p[i] 表示 $P$ 的 $i$ 次方。
接下来看进制哈希的一些应用。
最长回文串
使用进制哈希能够 $O(n\log n)$ 地求解查找长度为 $n$ 的字符串 $\mathrm{S}$ 中的最长回文子串的问题。
一个回文串是正向读和反向读都相同的串，为了利用哈希找到这样的串，先预处理出字符串 $\mathrm{S}$ 的所有前缀的哈希值，再把 $\mathrm{S}$ 倒过来得到 $\mathrm{T}$ ，预处理出 $\mathrm{T}$ 的所有前缀的哈希值。
如果 $\mathrm{S}$ 的某个子区间是一个回文串，那么对应 $\mathrm{T}$ 的子区间也是回文串，只要比较这两个区间的哈希值是否相等，若相等则说明找到了一个回文串。
这样扫描所有的子区间来查找回文子串，时间复杂度为 $O(n^2)$ 。
考虑用“中心扩展法”，以 $\mathrm{S}$ 的每个字符为中心，左右扩展，如果左右对应的字符相同，就是一个回文串。但如果只是简简单单的扩展，总时间复杂度还是 $O(n^2)$ 。左右两边的扩展的长度显然具有单调性，所以可以考虑用二分优化，这样可以优化到 $O(n\log n)$ 。
例题 洛谷P3501 [POI2010] ANT-Antisymmetry
对于一个01字符串，如果将这个字符串0和1取反后，再将整个串反过来和原串一样，就称作“反对称”字符串。比如00001111和010101就是反对称的，1001就不是。
现在给出一个长度为N的01字符串，求它有多少个子串是反对称的。
思路
其实就是求回文子串个数。
考虑用上面的中心扩展法，不过不是中心，而是左半部分和右半部分。
长度为 $l$ 则说明有 $l$ 个回文子串。
$O(n\log n)$ 二分查找每次累加 $l$ 即可。
代码
#include<bits/stdc++.h>
#define N 500010
#define ll long long
#define ull unsigned long long
using namespace std;
const ull P=131;
int n;
char s[N],t[N];
ull hs[N],ht[N],PP[N];
ll ans=0;
ull get_hash(ull *h,int L,int R) {
return h[R]-h[L-1]*PP[R-L+1];
}
bool check(int pos,int x) {
return get_hash(hs,pos-x+1,pos)==get_hash(ht,n-pos-x+1,n-pos);
}
void bnry_search(int pos) {
int l=0,r=min(pos,n-pos);
while(l<r) {
int mid=l+r+1>>1;
if(check(pos,mid)) l=mid;
else r=mid-1;
}
ans+=l;
}
void init() {
PP[0]=1;
for(int i=1;i<=n;i++) PP[i]=PP[i-1]*P;
for(int i=1;i<=n;i++) t[i]=(s[n-i+1]=='0'?'1':'0');
for(int i=1;i<=n;i++) hs[i]=hs[i-1]*P+s[i];
for(int i=1;i<=n;i++) ht[i]=ht[i-1]*P+t[i];
}
int main() {
scanf("%d",&n);
scanf("%s",s+1);
init();
for(int i=1;i<=n;i++) bnry_search(i);
printf("%lld\n",ans);
system("pause");
return 0;
}求循环节
例题 洛谷P4391 [BOI2009]Radio Transmission
给你一个字符串 $s_1$，它是由某个字符串 $s_2$ 不断自我连接形成的。但是字符串 $s_2$ 是不确定的，现在只想知道它的最短长度是多少。
思路
可以用哈希较为暴力地解决本题。
首先处理出所有前缀的哈希值。
然后开始枚举 $s_2$ 的长度 $i$ ，从 $1$ 到 $l$ ，每次不断检测后面的连续的长为 $i$ 的区间是否与 $s_1[1\dots i]$ 相等，最后在检测剩下的部分是否与 $s_1$ 的前面对应长度相等即可。
代码
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define N 1000010
using namespace std;
inline ll read() {
ll w=1,x=0;
char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return w*x;
}
const ull PP=131;
int l,ans;
char s[N];
ull H[N],P[N];
ull get_hash(int L,int R) {
return H[R]-H[L-1]*P[R-L+1];
}
void init() {
P[0]=1;
for(int i=1;i<=l;i++) P[i]=P[i-1]*PP;
for(int i=1;i<=l;i++) H[i]=H[i-1]*PP+s[i];
}
int main() {
l=read();
scanf("%s",s+1);
init();
for(int i=1;i<=l;i++) {
bool flag=true;
for(int j=1;(j+1)*i<=l;j++) {
if(get_hash(1,i)!=get_hash(1+i*j,i+i*j)) flag=false;
if(!flag) break;
}
int len=l%i;
if(len&&get_hash(1,len)!=get_hash(l-len+1,l)) flag=false;
if(flag) {
ans=i;
break;
}
}
printf("%d\n",ans);
system("pause");
return 0;
}参考资料
《算法竞赛》罗勇军
