本课时有配套视频讲解，购买后即可观看（永久有效）
字符串哈希函数的构造
一、课上练习
编程练习
二、知识总结
✨ 核心思想
字符串哈希是将一个字符串映射为一个整数（哈希值），使得：
- 相同的字符串一定有相同的哈希值
- 不同的字符串大概率有不同的哈希值
通过字符串哈希，可以在 $O(1)$ 时间内判断两个子串是否相等（预处理 $O(n)$），从而将许多需要逐字符比较的 $O(n)$ 操作优化为 $O(1)$。
核心方法是多项式滚动哈希（Polynomial Rolling Hash）：将字符串视为一个 $base$ 进制的数，对一个大质数取模。
✨ 算法原理
多项式哈希
对于字符串 $s = s0 s1 s2 \cdots s{n-1}$，定义哈希值为：
$$H(s) = \left(\sum{i=0}^{n-1} si \cdot base^{n-1-i}\right) \bmod mod$$
其中：
- $s_i$ 是字符的数值（通常取 ASCII 码或
s[i] - 'a' + 1） - $base$ 是基数（常取 131、13331 等质数）
- $mod$ 是模数（常取大质数如 $10^9+7$ 或 $10^9+9$）
前缀哈希与子串哈希
预处理前缀哈希数组 $H[i]$，表示 $s[0..i-1]$ 的哈希值：
$$H[i] = H[i-1] \times base + s[i-1]$$
则子串 $s[l..r]$ 的哈希值为：
$$hash(l, r) = H[r+1] - H[l] \times base^{r-l+1}$$
这样可以 $O(1)$ 计算任意子串的哈希值。
双哈希（Double Hashing）
单一哈希存在冲突的可能。为了将冲突概率降到极低，可以同时使用两组不同的 $(base, mod)$ 参数，只有两个哈希值都相同才判定为相同。
冲突概率分析：
- 单哈希：$\frac{1}{mod} \approx 10^{-9}$
- 双哈希：$\frac{1}{mod1 \times mod2} \approx 10^{-18}$，几乎不可能冲突
自然溢出哈希
利用 unsigned long long 的自然溢出（等价于对 $2^{64}$ 取模），省去手动取模的开销，速度极快。但由于模数固定且已知，可能被构造数据卡掉。
✨ 代码实现
基础字符串哈希
string_hash_basic.cpp
1#include <iostream>
2#include <string>
3using namespace std;
4
5typedef long long ll;
6const ll BASE = 131;
7const ll MOD = 1e9 + 7;
8const int MAXN = 100005;
9
10ll H[MAXN]; // 前缀哈希
11ll pw[MAXN]; // base 的幂次
12
13// 预处理
14void initHash(const string& s) {
15 int n = s.size();
16 pw[0] = 1;
17 H[0] = 0;
18 for (int i = 1; i <= n; i++) {
19 pw[i] = pw[i - 1] * BASE % MOD;
20 H[i] = (H[i - 1] * BASE + s[i - 1]) % MOD;
21 }
22}
23
24// 获取子串 s[l..r]（0-indexed）的哈希值
25ll getHash(int l, int r) {
26 return (H[r + 1] - H[l] * pw[r - l + 1] % MOD + MOD) % MOD;
27}
28
29int main() {
30 string s;
31 cin >> s;
32 initHash(s);
33
34 // 查询子串 [1, 3] 和 [5, 7] 是否相同
35 int l1, r1, l2, r2;
36 cin >> l1 >> r1 >> l2 >> r2;
37 if (getHash(l1, r1) == getHash(l2, r2))
38 cout << "两个子串相同" << endl;
39 else
40 cout << "两个子串不同" << endl;
41
42 return 0;
43}双哈希（推荐，竞赛安全版）
string_hash_double.cpp
1#include <iostream>
2#include <string>
3using namespace std;
4
5typedef long long ll;
6typedef pair<ll, ll> pll;
7
8const ll BASE1 = 131, MOD1 = 1e9 + 7;
9const ll BASE2 = 13331, MOD2 = 1e9 + 9;
10const int MAXN = 100005;
11
12ll H1[MAXN], H2[MAXN]; // 两组前缀哈希
13ll pw1[MAXN], pw2[MAXN];
14
15void initHash(const string& s) {
16 int n = s.size();
17 pw1[0] = pw2[0] = 1;
18 H1[0] = H2[0] = 0;
19 for (int i = 1; i <= n; i++) {
20 pw1[i] = pw1[i - 1] * BASE1 % MOD1;
21 pw2[i] = pw2[i - 1] * BASE2 % MOD2;
22 H1[i] = (H1[i - 1] * BASE1 + s[i - 1]) % MOD1;
23 H2[i] = (H2[i - 1] * BASE2 + s[i - 1]) % MOD2;
24 }
25}
26
27// 返回双哈希值
28pll getHash(int l, int r) {
29 ll h1 = (H1[r + 1] - H1[l] * pw1[r - l + 1] % MOD1 + MOD1) % MOD1;
30 ll h2 = (H2[r + 1] - H2[l] * pw2[r - l + 1] % MOD2 + MOD2) % MOD2;
31 return {h1, h2};
32}
33
34int main() {
35 string s;
36 cin >> s;
37 initHash(s);
38
39 int q;
40 cin >> q;
41 while (q--) {
42 int l1, r1, l2, r2;
43 cin >> l1 >> r1 >> l2 >> r2;
44 if (getHash(l1, r1) == getHash(l2, r2))
45 cout << "Yes" << endl;
46 else
47 cout << "No" << endl;
48 }
49 return 0;
50}自然溢出哈希
string_hash_overflow.cpp
1#include <iostream>
2#include <string>
3using namespace std;
4
5typedef unsigned long long ull;
6const ull BASE = 131;
7const int MAXN = 100005;
8
9ull H[MAXN], pw[MAXN];
10
11void initHash(const string& s) {
12 int n = s.size();
13 pw[0] = 1;
14 H[0] = 0;
15 for (int i = 1; i <= n; i++) {
16 pw[i] = pw[i - 1] * BASE; // 自然溢出，等价于 mod 2^64
17 H[i] = H[i - 1] * BASE + s[i - 1];
18 }
19}
20
21ull getHash(int l, int r) {
22 return H[r + 1] - H[l] * pw[r - l + 1]; // 自然溢出处理
23}应用：查找字符串中的重复子串
string_hash_application.cpp
1#include <iostream>
2#include <string>
3#include <unordered_set>
4using namespace std;
5
6typedef long long ll;
7const ll BASE = 131, MOD = 1e9 + 7;
8const int MAXN = 100005;
9
10ll H[MAXN], pw[MAXN];
11
12void initHash(const string& s) {
13 int n = s.size();
14 pw[0] = 1; H[0] = 0;
15 for (int i = 1; i <= n; i++) {
16 pw[i] = pw[i - 1] * BASE % MOD;
17 H[i] = (H[i - 1] * BASE + s[i - 1]) % MOD;
18 }
19}
20
21ll getHash(int l, int r) {
22 return (H[r + 1] - H[l] * pw[r - l + 1] % MOD + MOD) % MOD;
23}
24
25// 二分 + 哈希：求最长重复子串的长度
26int longestDupSubstring(const string& s) {
27 int n = s.size();
28 initHash(s);
29
30 int lo = 1, hi = n - 1, ans = 0;
31 while (lo <= hi) {
32 int mid = (lo + hi) / 2;
33 // 检查是否存在长度为 mid 的重复子串
34 unordered_set<ll> seen;
35 bool found = false;
36 for (int i = 0; i + mid - 1 < n; i++) {
37 ll h = getHash(i, i + mid - 1);
38 if (seen.count(h)) {
39 found = true;
40 break;
41 }
42 seen.insert(h);
43 }
44 if (found) {
45 ans = mid;
46 lo = mid + 1;
47 } else {
48 hi = mid - 1;
49 }
50 }
51 return ans;
52}
53
54int main() {
55 string s;
56 cin >> s;
57 cout << "最长重复子串长度: " << longestDupSubstring(s) << endl;
58 return 0;
59}✨ 执行示例
以字符串 s = "abcabc" 为例，$base = 131$，$mod = 10^9+7$：
1字符值: a=97, b=98, c=99
2
3前缀哈希计算:
4 H[0] = 0
5 H[1] = 0 × 131 + 97 = 97
6 H[2] = 97 × 131 + 98 = 12805
7 H[3] = 12805 × 131 + 99 = 1677554
8 H[4] = 1677554 × 131 + 97 = 219859671
9 H[5] = 219859671 × 131 + 98 = 28801616909 mod (10^9+7) = ...
10 H[6] = ...
11
12子串哈希:
13 hash("abc", [0,2]) = H[3] - H[0] × 131^3 = 1677554
14 hash("abc", [3,5]) = H[6] - H[3] × 131^3
15
16 两者相等 → 判定 s[0..2] == s[3..5] ✓
17
18验证: "abc" == "abc"，正确！✨ 解题步骤详解
适用场景
- 子串判等：$O(1)$ 判断两个子串是否相同
- 字符串匹配：Rabin-Karp 算法，$O(n+m)$ 的字符串搜索
- 最长公共子串：二分 + 哈希
- 回文判断：正向哈希与反向哈希比较
- 字符串去重/计数：用哈希值代替字符串存入集合
参数选择指南
| 参数 | 推荐值 | 说明 |
|---|---|---|
| base | 131, 13331 | 质数，大于字符集大小 |
| mod | $10^9+7$, $10^9+9$ | 大质数 |
| 字符映射 | s[i] - 'a' + 1 或 ASCII | 避免映射到 0 |
注意：字符不能映射为 0
如果 s[i] 的值为 0，那么 "a" 和 "aa" 的前缀会出现相同哈希值。常见做法是让 a 映射为 1 而非 0。
Rabin-Karp 字符串匹配
- 计算模式串 $p$ 的哈希值 $H_p$
- 在文本串 $t$ 上滑动窗口，计算每个长度为 $|p|$ 的子串哈希值
- 若 $H(t[i..i+|p|-1]) = H_p$，则匹配（可进一步验证避免冲突）
✨ 常见错误
- base 选得太小：如 $base = 26$，容易冲突。建议 $base \geq 131$
- 字符映射到 0：
'a' - 'a' = 0，会导致前导零问题，应映射为 1 - 取模时出现负数：
H[r+1] - H[l] * pw[...]可能为负，需要加 MOD - pw 数组忘记预处理：导致运行时错误或错误结果
- 数组大小不够：
H和pw的大小应为 $n+1$ - 单哈希被卡：在特定平台（如 CF）上应使用双哈希或随机 base
- 自然溢出哈希被构造数据：模数 $2^{64}$ 是已知的，可以被专门构造的数据碰撞
✨ 算法评价
时间复杂度
| 操作 | 时间 |
|---|---|
| 预处理 | $O(n)$ |
| 查询子串哈希 | $O(1)$ |
| Rabin-Karp 匹配 | $O(n + m)$ |
| 二分+哈希求最长重复子串 | $O(n \log n)$ |
空间复杂度
$O(n)$，存储前缀哈希和幂次数组。
与其他字符串算法的比较
| 算法 | 用途 | 预处理 | 查询 |
|---|---|---|---|
| 字符串哈希 | 子串判等 | $O(n)$ | $O(1)$ |
| KMP | 模式匹配 | $O(m)$ | $O(n)$ |
| 后缀数组 | 各种子串问题 | $O(n \log n)$ | $O(\log n)$ |
| 字典树 | 前缀查询 | $O(\sum | s_i |
字符串哈希的优势在于实现简单、适用范围广，是竞赛中最常用的字符串工具之一。