字符串哈希

定义

定义一个把字符串映射到整数的函数 $f$ ，称为 Hash 函数。我们希望这个函数可以方便地判断两个字符串是否相等。

核心思想

将字符串视为一个 $b$ 进制数，对一个大质数 $M$ 取模：

$f (s) = \sum_{i = 1}^{l} s [i] \times b^{l - i} (mod M)$

例如字符串 $x y z$ 的哈希值为 $x b^{2} + y b + z$ 。

参数	常见取值	说明
基数 $b$	131, 233, 91138233	大于字符集大小的质数
模数 $M$	$1 0^{9} + 7$ , $1 0^{9} + 9$	大质数，双哈希用两个不同模数
自然溢出	`unsigned long long`	模 $2^{64}$ ，效率高但有被卡风险

子串哈希 O(1) 查询

预处理前缀哈希 $h [i] = f (s [1.. i])$ ，则子串 $s [l .. r]$ 的哈希值为：

$f (s [l .. r]) = h [r] - h [l - 1] \times b^{r - l + 1} (mod M)$

using ull = unsigned long long;
constexpr int B = 131;
constexpr ull M = 1e9 + 7;
vector<ull> h(n + 1), pw(n + 1);
pw[0] = 1;
for (int i = 1; i <= n; i++) {
    pw[i] = pw[i-1] * B % M;
    h[i] = (h[i-1] * B + s[i-1]) % M;
}
auto get = [&](int l, int r) {
    return (h[r] - h[l-1] * pw[r-l+1] % M + M) % M;
};

双哈希

用两个不同模数分别计算，两个哈希值都相等才认为字符串相同，将冲突概率降到极低。

哈希的冲突

生日悖论: 当比较的字符串数量 $n$ 增大时，冲突概率平方级上升
$p (n, d) \approx 1 - exp (- n (n - 1) / (2 d))$ ，其中 $d$ 为值域大小
自然溢出 在 $b$ 为偶数时可被构造碰撞
大模数 可用双哈希抵御

应用场景

字符串匹配（O(n+m) 预处理 + O(1) 比较）
允许 k 次失配的匹配（哈希 + 二分失配位置）
最长回文子串（正反哈希 + 二分）
不同子串数量
最长公共子串（二分长度 + 哈希集合）

平台	编号	名称
洛谷	P3370	字符串哈希（模板）
洛谷	P2757	等差数列
Codeforces	1200E	Compress Words

多平台练习

RootStack

探索

字符串哈希

字符串哈希

定义

核心思想

子串哈希 O(1) 查询

双哈希

哈希的冲突

应用场景

推荐练习题

相关链接

多平台练习

关系图谱

目录