基本介绍
字符串哈希的主要思路是这样的：首先选定一个进制 \(P\)，对于一个长度为 \(N\) 的字符串 \(S\) 的所有 \(i(1\leq i \leq n)\) 的 \(S_1,S_2,...,S_i\) 子串表示成 \(P\) 进制的值预处理记录下来。这样判断 \(S_i,S_{i+1},...,S_{i+m-1}\) 和 \(T_1,T_2,...,T_m\) 是否相等的时候就可以直接以这两段的哈希值作为判断依据。显然如果两个字符串相等那么对于同一个模数这两段的哈希值是相等的。
具体如何计算 \(S_l,S_{l+1},...,S{r}\) 的哈希值呢？根据进制的定义，哈希值等于 \(H_r-H_{l-1}\times P^{r-l+1}\)，其中 \(H_i\) 表示 \(1\) 到 \(i\) 的哈希值。具体类比带入一个十进制整数可以帮助更好的理解。
实现方法
自然溢出
显然如果字符串稍微长一点那么普通的 int 啥的就存不下了。我们需要进行取模。
一个讨巧的做法是直接不管他，不取模。因为在 C++ 中如果一个数大于该类型的最大值那么就会溢出从最小值继续开始算，相当于对该类型的值域取模。
但由于模数的固定性，这个很容易被卡（构造两个不同的字符串但是在特定模数下哈希值相同，进制不影响大多数构造方法）。
单模哈希
所以我们就选择一个特定的模数对哈希值进行取模即可。注意减法时值不要变成负数（可以通过加上模数再减再取模解决）。
多模哈希
根据抽屉原理我们可以证明，对于一个 \(10^9\) 级别的模数，一个 \(10^5\) 长度的字符串会有两个子串哈希值相同。
所以我们可以通过增加模数的方式提高正确率。如两个 \(10^{9}\) 级别的模数同时哈希，要两种哈希方式值都一样才判断子串相同，那就等同于模数是 \(10^{18}\) 级别的。这时候纯随机要出错就得串长 \(10^9\) 了。所以一般双模哈希可以保证正确。
关于模数和进制
模数和进制直接决定着字符串哈希的正确率。给出几点建议：
-
尽量选择质数。尤其不要使用类似 \(2^n\) 的进制数，极其容易冲突。
-
重要比赛不要写自然溢出，容易被卡。
-
不要使用人尽皆知的模数，如 \(998244353,10^9+7\)。可能有良心数据人照着卡。进制数无所谓。
大质数表以供参考。
多维字符串
类似高维前缀和的写法，每一维单独相加，模数不同。也可以类似二维前缀和的写法。
例题
例2.1：字符串匹配
题意
有两个字符串 \(S\) 和 \(T\),求字符串 \(T\) 在 \(S\) 中出现了几次。
题解
把 \(S\) 的哈希值算出来，然后依次比较 \(S_i,S_{i+1},...,S_{i+m-1}(1\leq i,i+m-1\leq n)\) 的哈希值是否等于 \(T\) 的哈希值。
单模可以过。因为只有 \(n\) 级别的子串。
代码
#include<bits/stdc++.h>
#define p 131
#define mod 1000001011
#define int long long
using namespace std;
string s,t;
int n,m,ht,ans,h[1000005],base[1000005];
signed main(){
cin>>s>>t;
n=s.length(),m=t.length();
s='#'+s,t='#'+t;
base[0]=1;
for(int i=1;i<=n;i++) h[i]=(h[i-1]*p%mod+s[i])%mod,base[i]=base[i-1]*p%mod;
for(int i=1;i<=m;i++) ht=(ht*p+t[i])%mod;
for(int i=1;i+m-1<=n;i++) if((h[i+m-1]+mod-h[i-1]*base[m]%mod)%mod==ht) ans++;
cout<<ans;
return 0;
}
例2.2：两个后缀的最长公共前缀
题意
给定一个长度为 \(N\) 的字符串 \(S\)，下标从 \(1\) 开始。有 \(Q\) 个询问，每次询问有两个整数 \(x\) 和 \(y\)，求 \(S[x...n]\) 和 \(S[y...n]\) 的最长公共前缀，即从 \(x\) 和 \(y\) 开始有多少个字母是相同的。
题解
算出 \(S\) 的哈希值，然后二分最长的长度，按题意比较就可以了。复杂度 \(O(Q\log N+N)\)。
代码
#include<bits/stdc++.h>
#pragma GCC optimize(2,3,"inline","-Ofast")
#define p 131
#define mod 1000001011
#define int unsigned long long
using namespace std;
string s;
int n,q,h[100005],base[100005];
int get(int i,int m){
return (h[i+m-1]+mod-h[i-1]*base[m]%mod)%mod;
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>q>>s;
s='#'+s;
base[0]=1;
for(int i=1;i<=n;i++) h[i]=(h[i-1]*p%mod+s[i])%mod,base[i]=base[i-1]*p%mod;
while(q--){
int x,y;
cin>>x>>y;
if(x>y) swap(x,y);
int l=0,r=n-y+1,ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(get(x,mid)==get(y,mid)) l=mid+1,ans=mid;
else r=mid-1;
}
cout<<ans<<'\n';
}
}
例2.3 最长回文
题意
求一个字符串的最长回文子串。
题解
和上一题相似的，预处理字符串正着和反着的哈希值，对于原字符串的每一位二分这一位作为回文串的最中间可以达到的最大回文长度。也就是判断从这位往左和往右相同长度的子串反着、正着的哈希值是否相等。注意分讨回文串长度为偶数的情况。复杂度 \(O(N\log N)\)。
代码
#include<bits/stdc++.h>
#pragma GCC optimize(2,3,"inline","-Ofast")
#define p 131
#define mod 1000001011
#define int long long
using namespace std;
string s;
int n,h1[1000005],h2[1000005],base[1000005];
int get1(int i,int m){
return (h2[i]+mod-h2[i+m]*base[m]%mod)%mod;
}
int get2(int i,int m){
return (h1[i+m-1]+mod-h1[i-1]*base[m]%mod)%mod;
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>s;
s='#'+s;
base[0]=1;
for(int i=1;i<=n;i++) h1[i]=(h1[i-1]*p%mod+s[i])%mod,base[i]=base[i-1]*p%mod;
for(int i=n;i>=1;i--) h2[i]=(h2[i+1]*p%mod+s[i])%mod;
int ans=0;
for(int i=1;i<=n;i++){
int l=0,r=min(i,n-i+1);
while(l<=r){
int mid=(l+r)>>1;
if(get1(i-mid+1,mid)==get2(i,mid)) l=mid+1,ans=max(ans,mid*2-1);
else r=mid-1;
}
if(i<n){
l=0,r=min(i,n-i);
while(l<=r){
int mid=(l+r)>>1;
if(get1(i-mid+1,mid)==get2(i+1,mid)) l=mid+1,ans=max(ans,mid*2);
else r=mid-1;
}
}
}
cout<<ans<<'\n';
}
例2.4：二维匹配
题意
给定一个 \(M\) 行 \(N\) 列的 01 矩阵，以及 \(Q\) 个 \(A\) 行 \(B\) 列的01矩阵，你需要求出这 \(Q\) 个矩阵哪些在原矩阵中出现过。
题解
算出所有端点为左上角的子矩阵的哈希值存进 map 里，暴力检查新的矩阵哈希值是否存在即可。复杂度 \(O(NM\log NM+QAB\log NM)\)。
代码
#include<bits/stdc++.h>
#define p1 131
#define p2 13331
#define int long long
using namespace std;
int n,m,q,a,b,h1[1005][1005],h2[1005][1005],base1[1005],base2[1005];
string s[1005],t[1005];
map<int,bool> mp;
signed main(){
cin>>n>>m>>a>>b;
base1[0]=base2[0]=1;
for(int i=1;i<=n;i++) cin>>s[i],s[i]='#'+s[i];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
h1[i][j]=h1[i][j-1]*p1+s[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
h1[i][j]+=h1[i-1][j]*p2;
}
}
for(int i=1;i<=n;i++){
base1[i]=base1[i-1]*p1;
base2[i]=base2[i-1]*p2;
}
for(int i=a;i<=n;i++){
for(int j=b;j<=m;j++){
int v1=h1[i][j];
int v2=h1[i-a][j]*base2[a];
int v3=h1[i][j-b]*base1[b];
int v4=h1[i-a][j-b]*base2[a]*base1[b];
mp[v1-v2-v3+v4]=1;
}
}
cin>>q;
while(q--){
for(int i=1;i<=a;i++) cin>>t[i],t[i]='#'+t[i];
for(int i=1;i<=a;i++){
for(int j=1;j<=b;j++) h2[i][j]=h2[i][j-1]*p1+t[i][j];
}
for(int i=1;i<=a;i++){
for(int j=1;j<=b;j++) h2[i][j]+=h2[i-1][j]*p2;
}
cout<<mp[h2[a][b]]<<'\n';
}
}