字符串 Hash，将原字符串映射到一个正整数上，并且保证不同的字符串得到的哈希值大概率不同，以此快速判断字符串是否相等。

在算法竞赛中，字符串哈希最特殊的操作在于，O(n) 预处理后可以 O(1) 复杂度得到任意子串的哈希值，从而可以判断子串匹配、回文等操作。

算法解释

基本思想

基本思想是将字符串代入一个多项式的系数中。例如，设 b 为一个给定的常数（称为基数），M 为一个大模数，字符串 s 的长度为 n，则 s 的 Hash 值可以表示为

为了防止卡 Hash，可以取定两个基和模数，分别计算 Hash。

子串的 Hash

我们可以用 O(n) 的复杂度预处理字符串前缀的 Hash。由定义，有：

此时，子串的 Hash 为：

由此可以快速判断两个子串是否相等。

代码

预处理 pow_b 和 hash_preprocess 后，使用 substr_hash 得到某个子串的 Hash 值。

constexpr size_t MAXN = 5e3 + 5;
using ull = unsigned long long;

constexpr size_t B = 233, M = 748087387;
ull prefix_hash[MAXN], pow_b[MAXN];
size_t n;

void init_pow_b()
{
    pow_b[0] = 1;
    for (size_t i = 1; i < MAXN; i++)
    {
        pow_b[i] = pow_b[i - 1] * B % M;
    }
}

void hash_preprocess(string s)
{
    size_t n = s.length();
    prefix_hash[0] = 0;
    for (size_t i = 1; i <= n; i++)
    {
        prefix_hash[i] = (prefix_hash[i - 1] * B + s[i - 1]) % M;
    }
}

ull substr_hash(size_t l, size_t r, size_t n = ::n)
{
    return (M + prefix_hash[r] - prefix_hash[l - 1] * pow_b[r - l + 1] % M) % M;
}

应用

字符串匹配

预处理原串和子串的 Hash 后，可以在 O(n) 时间内寻找字符串的匹配，和 KMP 算法效率相同。

回文子串判断

O(n) 预处理字符串和反转字符串的前缀 Hash，然后比较字符串和反转字符串相应位置的 Hash 值是否相等，即可判断某个子串是否回文，复杂度 O(1)。