字符串哈希

定义

hash，其实就是将一个东西映射成另一个东西，类似Map，key对应value。

那么字符串Hash，其实就是：构造一个数字使之唯一代表一个字符串。将映射关系进行一一对应，也就是一个字符串对应一个数字，那么一个数字也对应一个字符串。

用字符串Hash的目的是，我们如果要比较一个字符串，我们不直接比较字符串，而是比较它对应映射的数字，这样子就知道两个“子串”是否相等。从而达到，子串的Hash值的时间为 O(1)，进而可以利用“空间换时间”来节省时间复杂度。

构造字符串哈希

将字符串映射成数字，和我们平时的将一个某Base进制数，变为一个十进制数相类似。

介绍两种方法，每一种方法，主要都是用使用 Base 和 Mod（都要求是素数），在这里我们要尽量把MOD和Base取大。这种情况下，冲突（即不同字符串却有着相同的hash值）的概率是很低的。

常用Base：127,131,13331

常用Mod：1e9+7,1e9+9,19260817,998244353

下文的约定

#define int long long

const int N=1e5+10,base=13331,mod=1e9+7;
int h[N], p[N];
h[0] = 0;
p[0] = 1;

这里的 $hash$ 数组表示子串 $[0,i]$ 的哈希值，$p[i]$ 表示 $Bas{e}^i$，所以把 $hash[0]$ 初始化为 0，$p[0]$ 初始化为 1。

假如给你一个数字1166，形式上你只知道它只是1和6的组合，但你知道它代表的实际大小为$1\ast 10^3+1\ast 10^2+6\ast 10^1+6\ast 10^0$

同理，给你一个字符串，要把它转换为数字，就可以先把每一个字符都先对应一个数字，然后把它们按照顺序乘以进制（Base）的幂进行相加，然后这个数可能很大，所以一般会取余数（MOD）。

单哈希

单哈希只对字符串做一次哈希，其递推公式为：
$$h[i]=(h[i-1]\times Base+s[i])(\mathrm{mod}MOD)$$
我们通过迭代的方式就可以算出每一个子串的哈希值了。

获取子串

我们得到的 Hash值都是前 i 个字符的字串，利用前缀Hash值，我们可以O(1) 时间来获取某个 $[l,r]$ 字串。
$$h[l,r]=h[r]-h[l-1]\times p^{r-l+1}$$

模板题：字符串哈希

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10,base=13331,mod=1e9+7;
int h[N],p[N],n,m;
string s;
int ask(int l,int r){
    return (h[r]-(h[l-1]*p[r-l+1]%mod)+mod)%mod;
}
void solve() {
    cin>>n>>m>>s;
    s='#'+s;
    p[0]=1;
    for(int i=1;i<=n;i++){
        h[i]=(h[i-1]*base+s[i])%mod;
        p[i]=(p[i-1]*base)%mod;
    }
    while(m--){
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        if(ask(l1,r1)==ask(l2,r2)){
            cout<<"Yes"<<'\n';
        }else{
            cout<<"No"<<'\n';
        }
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T=1;
//    cin>>T;
    while(T--) solve();
    return 0;
}

Hash重要应用：最长回文子串

枚举每个字符为回文中心，判断正反向哈希是否相等来判断是否是回文，由于有了哈希可以快速判断子串是否相等，对半径使用二分法搜索，时间复杂度 O(nlogn)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10,base=13331,mod=1e9+7;
int h[N],p[N],n,h1[N];
string s,t;
int ask(int l,int r){
    return (h[r]-(h[l-1]*p[r-l+1]%mod)+mod)%mod;
}
int ask1(int l,int r){
    return (h1[r]-(h1[l-1]*p[r-l+1]%mod)+mod)%mod;
}
void solve() {
    getline(cin,s);
    n=s.size();
    t=s;
    reverse(t.begin(),t.end());
    t='#'+t;
    s='#'+s;
    p[0]=1;
    for(int i=1;i<=n;i++){
        h[i]=(h[i-1]*base+s[i])%mod;
        h1[i]=(h1[i-1]*base+t[i])%mod;
        p[i]=(p[i-1]*base)%mod;
    }
    int ans=1;
    for(int i=1;i<=n;i++){
        int l=0,r=min(i-1,n-i);
        while(l<=r){
            int mid=l+r>>1;
            if(ask(i-mid,i-1)==ask1(n-(i+mid)+1,n-(i+1)+1)){
                l=mid+1;
                ans=max(ans,2*mid+1);
            }else{
                r=mid-1;
            }
        }
        l=0,r=min(i,n-i);
        while(l<=r){
            int mid=l+r>>1;
            if(ask(i-mid+1,i)==ask1(n-(i+mid)+1,n-(i+1)+1)){
                l=mid+1;
                ans=max(ans,2*mid);
            }else{
                r=mid-1;
            }
        }
    }
    cout<<ans<<'\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T=1;
//    cin>>T;
    while(T--) solve();
    return 0;
}

双哈希

双哈希就是用两个模数和两个素数对一个字符串算两次哈希，得到一个pair，用pair做比较，避免哈希碰撞。