字符串哈希详述

前言

03-08 字符串哈希 已经介绍了字符串哈希的基本原理：$H(S) = \sum S_i \cdot B^{i} \bmod M$，以及如何用前缀哈希 $O(1)$ 求子串哈希。这篇是进阶篇，聚焦在实际应用和工程细节上。

字符串哈希最大的威力在于：把字符串比较变成整数比较。两个子串是否相同？直接比较哈希值。子串是否是回文？正向哈希和反向哈希各算一次。在字符串里找一个模式串？把模式串的哈希和每个等长子串的哈希比较。这些问题都可以在 $O(1)$ 或 $O(N)$ 内解决——前提是哈希不冲突。

问题的本质

哈希冲突怎么办？

单个 $(B, M)$ 的冲突概率是 $O(1/M)$。如果 $M = 10^9+7$，冲突概率约 $10^{-9}$。做 $10^5$ 次查询，期望冲突次数约 $10^{-4}$——看起来安全，但在竞赛中一次冲突就意味着 WA。

双哈希（Double Hashing）是标准解决方案：用两组不同的 $(B_1, M_1)$ 和 $(B_2, M_2)$ 分别计算哈希。两个哈希同时冲突的概率是 $O(1/M_1 \cdot 1/M_2)$。比如 $M_1 = 10^9+7, M_2 = 10^9+9$，冲突概率降到 $10^{-18}$，完全可以忽略。

正向哈希与反向哈希

回文判定需要比较 $S[l \ldots r]$ 和它的反转 $S[r \ldots l]$。做法：对原串 $S$ 计算正向哈希 $H_1$，对反转串 $S^R$ 计算反向哈希 $H_2$。$S[l \ldots r]$ 是回文 $\iff$ $H_1(l,r) = H_2(N+1-r, N+1-l)$。

理论 + 代码

双哈希模板

#include <cstdio>
#include <cstring>
using namespace std;

const long long MOD1 = 1000000007;
const long long MOD2 = 1000000009;
const long long B1 = 1000007;
const long long B2 = 1000009;

long long power1[100009], power2[100009];
long long h1[100009], h2[100009];

void init_hash(const char* S, int N) {
    power1[0] = 1; power2[0] = 1;
    for (int i = 1; i <= N; i++) {
        power1[i] = power1[i-1] * B1 % MOD1;    // ① 预计算 B^i
        power2[i] = power2[i-1] * B2 % MOD2;
    }
    h1[0] = 0; h2[0] = 0;
    for (int i = 1; i <= N; i++) {
        h1[i] = (h1[i-1] * B1 + S[i-1]) % MOD1; // ② 前缀哈希
        h2[i] = (h2[i-1] * B2 + S[i-1]) % MOD2;
    }
}

// ③ 子串 [l, r] 的哈希 (0-indexed)
long long get_hash1(int l, int r) {
    long long val = (h1[r+1] - h1[l] * power1[r-l+1] % MOD1 + MOD1) % MOD1;
    return val;
}
long long get_hash2(int l, int r) {
    long long val = (h2[r+1] - h2[l] * power2[r-l+1] % MOD2 + MOD2) % MOD2;
    return val;
}

逐行解析：

• ① 预计算 $B^i \bmod M$，后续子串哈希需要用。
• ② 前缀哈希：$h[i] = h[i-1] \times B + S[i]$。
• ③ 子串哈希：$hash(S[l \ldots r]) = h[r+1] - h[l] \times B^{r-l+1}$。+MOD 防止负数。

回文判定（正向+反向哈希）

教材 8.6 节 B56 的方法：对 $S$ 和 $S$ 的反转分别建立哈希。子串 $S[l \ldots r]$ 是回文 $\iff$ 正向哈希等于反向哈希。

char S[100009], SRev[100009];
long long hL1[100009], hL2[100009]; // 正向
long long hR1[100009], hR2[100009]; // 反向

// 回文判定：S[L..R] 是否是回文 (1-indexed)
bool is_palindrome(int L, int R, int N) {
    // 正向哈希
    long long v1 = (hL1[R] - hL1[L-1] * power1[R-L+1] % MOD1 + MOD1) % MOD1;
    long long v2 = (hL2[R] - hL2[L-1] * power2[R-L+1] % MOD2 + MOD2) % MOD2;
    // 反向哈希：SRev[N+1-R .. N+1-L]
    int rL = N + 1 - R, rR = N + 1 - L;
    long long v3 = (hR1[rR] - hR1[rL-1] * power1[rR-rL+1] % MOD1 + MOD1) % MOD1;
    long long v4 = (hR2[rR] - hR2[rL-1] * power2[rR-rL+1] % MOD2 + MOD2) % MOD2;
    return (v1 == v3 && v2 == v4);                 // ① 双哈希比较
}

逐行解析：

• 反向串 $S^R$ 中，原串的 $S[L \ldots R]$ 对应 $S^R[N+1-R \ldots N+1-L]$。
• ① 四个哈希值全部相等才判定为回文，冲突概率极低。

例题

例题 1：TB A56 — String Hash（子串比较）

题目：长度 $N$ 的字符串 $S$，$Q$ 次查询：$S[a_i, b_i]$ 和 $S[c_i, d_i]$ 是否相同？

数据范围：$1 \le N, Q \le 2 \times 10^5$

—— AtCoder Tessoku Book A56

分析：双哈希模板题。对每个查询比较两个子串的哈希值。

输入样例：

7 3
abcbabc
1 3 5 7
1 5 2 6
1 2 6 7

输出：Yes / No / No

代码：

#include <cstdio>
#include <cstring>
using namespace std;

const long long MOD1 = 1000000007;
const long long MOD2 = 1000000009;
const long long B1 = 1000007, B2 = 1000009;

long long pw1[200009], pw2[200009];
long long h1[200009], h2[200009];
char S[200009];

int main() {
    int N, Q;
    scanf("%d%d", &N, &Q);
    scanf("%s", S);

    pw1[0] = pw2[0] = 1;
    for (int i = 1; i <= N; i++) {
        pw1[i] = pw1[i-1] * B1 % MOD1;              // ① 预计算幂
        pw2[i] = pw2[i-1] * B2 % MOD2;
    }
    h1[0] = h2[0] = 0;
    for (int i = 0; i < N; i++) {
        h1[i+1] = (h1[i] * B1 + S[i]) % MOD1;       // ② 前缀哈希
        h2[i+1] = (h2[i] * B2 + S[i]) % MOD2;
    }

    while (Q--) {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        a--; b--; c--; d--;                          // ③ 转 0-indexed
        int len = b - a + 1;
        // ④ 子串哈希
        long long v1 = (h1[b+1] - h1[a] * pw1[len] % MOD1 + MOD1) % MOD1;
        long long v2 = (h2[b+1] - h2[a] * pw2[len] % MOD2 + MOD2) % MOD2;
        long long v3 = (h1[d+1] - h1[c] * pw1[len] % MOD1 + MOD1) % MOD1;
        long long v4 = (h2[d+1] - h2[c] * pw2[len] % MOD2 + MOD2) % MOD2;
        printf("%s\n", (v1 == v3 && v2 == v4) ? "Yes" : "No");
    }
}

逐行解析：

• ①② 预处理：$O(N)$。
• ③ 输入是 1-indexed，转成 0-indexed 方便处理。
• ④ 子串哈希公式：$hash(S[a \ldots b]) = h[b+1] - h[a] \times B^{len}$。

验证：$S$ = “abcbabc”。查询 $(1,3)$ vs $(5,7)$：$S[1..3]$=“abc”, $S[5..7]$=“abc”。哈希相同 → Yes。✓

---

例题 2：TB B56 — Palindrome Queries（回文判定）

题目：长度 $N$ 的字符串 $S$，$Q$ 次查询：$S[L_i, R_i]$ 是否是回文？

数据范围：$1 \le N, Q \le 10^5$

—— AtCoder Tessoku Book B56

分析：教材 8.6 节原题。对 $S$ 和 $S^R$ 分别建双哈希，每次查询比较正向和反向哈希。

输入样例：

11 3
mississippi
5 8
6 10
2 8

输出：Yes / No / Yes

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const long long MOD1 = 1000000007;
const long long MOD2 = 1000000009;
const long long B1 = 1000007, B2 = 1000009;

long long pw1[100009], pw2[100009];
long long hL1[100009], hL2[100009]; // 正向
long long hR1[100009], hR2[100009]; // 反向
char S[100009], SRev[100009];

int main() {
    int N, Q;
    scanf("%d%d", &N, &Q);
    scanf("%s", S);
    for (int i = 0; i < N; i++) SRev[i] = S[N-1-i]; // ① 反转字符串
    SRev[N] = '\0';

    pw1[0] = pw2[0] = 1;
    for (int i = 1; i <= N; i++) {
        pw1[i] = pw1[i-1] * B1 % MOD1;
        pw2[i] = pw2[i-1] * B2 % MOD2;
    }
    hL1[0] = hL2[0] = hR1[0] = hR2[0] = 0;
    for (int i = 0; i < N; i++) {
        hL1[i+1] = (hL1[i] * B1 + S[i]) % MOD1;    // ② 正向前缀哈希
        hL2[i+1] = (hL2[i] * B2 + S[i]) % MOD2;
        hR1[i+1] = (hR1[i] * B1 + SRev[i]) % MOD1;  // ③ 反向前缀哈希
        hR2[i+1] = (hR2[i] * B2 + SRev[i]) % MOD2;
    }

    while (Q--) {
        int L, R;
        scanf("%d%d", &L, &R);
        L--; R--;                                     // ④ 转 0-indexed
        int len = R - L + 1;
        // ⑤ 正向哈希
        long long v1 = (hL1[R+1] - hL1[L] * pw1[len] % MOD1 + MOD1) % MOD1;
        long long v2 = (hL2[R+1] - hL2[L] * pw2[len] % MOD2 + MOD2) % MOD2;
        // ⑥ 反向哈希：SRev[N-1-R .. N-1-L]
        int rL = N - 1 - R, rR = N - 1 - L;
        long long v3 = (hR1[rR+1] - hR1[rL] * pw1[len] % MOD1 + MOD1) % MOD1;
        long long v4 = (hR2[rR+1] - hR2[rL] * pw2[len] % MOD2 + MOD2) % MOD2;
        printf("%s\n", (v1 == v3 && v2 == v4) ? "Yes" : "No");
    }
}

逐行解析：

• ① 反转字符串。$S^R[i] = S[N-1-i]$。
• ②③ 对 $S$ 和 $S^R$ 分别建立双哈希前缀数组。
• ⑤⑥ 正向子串 $S[L \ldots R]$ 对应反向子串 $S^R[N-1-R \ldots N-1-L]$。两者哈希相等即为回文。

验证：$S$ = “mississippi”。查询 $(5,8)$：$S[5..8]$=“issi”→反转也是”issi”→回文→Yes。$(6,10)$：“ssipp”→反转”ppiss”≠“ssipp”→不是→No。$(2,8)$：“ississi”→反转”ississi”→回文→Yes。✓

---

例题 3：Rabin-Karp 字符串匹配

场景：文本串 $T$（长度 $N$）和模式串 $P$（长度 $M$）。找出 $P$ 在 $T$ 中所有出现位置。

数据范围：$1 \le N, M \le 10^6$

分析：计算 $P$ 的哈希值，然后对 $T$ 的每个长度为 $M$ 的子串计算哈希并比较。总时间 $O(N+M)$。

代码：

#include <cstdio>
#include <cstring>
using namespace std;

const long long MOD = 1000000007;
const long long B = 1000007;

long long pw[1000009], h[1000009];
char T[1000009], P[1000009];

int main() {
    scanf("%s%s", T, P);
    int N = strlen(T), M = strlen(P);

    pw[0] = 1;
    for (int i = 1; i <= N; i++) pw[i] = pw[i-1] * B % MOD;
    h[0] = 0;
    for (int i = 0; i < N; i++)
        h[i+1] = (h[i] * B + T[i]) % MOD;           // ① T 的前缀哈希

    long long hashP = 0;
    for (int i = 0; i < M; i++)
        hashP = (hashP * B + P[i]) % MOD;            // ② P 的哈希

    for (int i = 0; i + M <= N; i++) {
        long long val = (h[i+M] - h[i] * pw[M] % MOD + MOD) % MOD; // ③ 子串哈希
        if (val == hashP) printf("%d\n", i);          // ④ 匹配
    }
}

逐行解析：

• ② 计算模式串 $P$ 的哈希值。
• ③ 对 $T$ 的每个起点 $i$，$O(1)$ 计算长度为 $M$ 的子串哈希。
• ④ 哈希值匹配则输出位置。单哈希可能有冲突，实际使用建议双哈希。

---

例题 4：最长公共子串（二分+哈希）

场景：两个字符串 $S$ 和 $T$，求最长公共子串的长度。

数据范围：$1 \le |S|, |T| \le 10^5$

分析：二分答案 $L$（最长公共子串长度）。对每个 $L$，把 $S$ 的所有长度为 $L$ 的子串哈希存入 set，然后检查 $T$ 的每个长度为 $L$ 的子串是否在 set 中。总时间 $O((N+M) \log \min(N,M))$。

代码：

#include <cstdio>
#include <cstring>
#include <set>
using namespace std;

const long long MOD = 1000000007;
const long long B = 1000007;
long long pw[100009], hS[100009], hT[100009];
char S[100009], T[100009];

// 获取子串哈希
long long get_hash(long long* h, int l, int len) {
    return (h[l+len] - h[l] * pw[len] % MOD + MOD) % MOD;
}

bool check(int L, int NS, int NT) {
    set<long long> st;
    for (int i = 0; i + L <= NS; i++)
        st.insert(get_hash(hS, i, L));                // ① S 的所有长度 L 子串
    for (int i = 0; i + L <= NT; i++)
        if (st.count(get_hash(hT, i, L))) return true; // ② T 中找到匹配
    return false;
}

int main() {
    scanf("%s%s", S, T);
    int NS = strlen(S), NT = strlen(T);
    int N = max(NS, NT);
    pw[0] = 1;
    for (int i = 1; i <= N; i++) pw[i] = pw[i-1] * B % MOD;
    for (int i = 0; i < NS; i++) hS[i+1] = (hS[i] * B + S[i]) % MOD;
    for (int i = 0; i < NT; i++) hT[i+1] = (hT[i] * B + T[i]) % MOD;

    int lo = 0, hi = min(NS, NT), ans = 0;
    while (lo <= hi) {                                 // ③ 二分答案
        int mid = (lo + hi) / 2;
        if (check(mid, NS, NT)) { ans = mid; lo = mid + 1; }
        else hi = mid - 1;
    }
    printf("%d\n", ans);
}

逐行解析：

• ① 把 $S$ 的所有长度为 $L$ 的子串哈希存入 set。
• ② 遍历 $T$ 的所有长度为 $L$ 的子串，检查是否有匹配。
• ③ 二分最长公共子串长度。每次 check 耗时 $O(N \log N)$，总时间 $O(N \log^2 N)$。

参考文献

教材讲解 — 競技プログラミングの鉄則 第 8 章

• 8.6 B56 Palindrome Queries（字符串哈希+回文判定 解说）

系统练习 — 競技プログラミングの鉄則

• A56 String Hash（子串比较）【例题】
• B56 Palindrome Queries（回文判定）【例题】

---

系列索引

第零章 基础工具

• 00-01 复杂度与暴力枚举
• 00-02 排序
• 00-03 累积和与差分

第一章 搜索技术

• 01-01 二分搜索
• 01-02 双指针与尺取法

第二章 数学基础

• 02-01 整数与整除
• 02-02 素数与筛法
• 02-03 同余与模运算
• 02-04 快速幂与逆元
• 02-05 组合计数
• 02-06 容斥原理
• 02-07 欧拉函数
• 02-08 博弈论基础

第三章 数据结构

• 03-01 栈、队列与单调栈
• 03-02 堆与优先队列
• 03-03 并查集
• 03-04 树状数组
• 03-05 线段树
• 03-06 懒标记线段树
• 03-07 Sparse Table 与倍增
• 03-08 字符串哈希

第四章 图论

• 04-01 图的遍历
• 04-02 最短路—Dijkstra 与 01-BFS
• 04-03 最短路—Bellman-Ford 与 Floyd
• 04-04 拓扑排序
• 04-05 最小生成树
• 04-06 强连通分量与 2-SAT
• 04-07 二分图与网络流
• 04-08 树上问题

第五章 动态规划

• 05-01 DP入门—状态与转移
• 05-02 背包问题族
• 05-03 LIS、LCS与编辑距离
• 05-04 区间DP
• 05-05 状态压缩DP
• 05-06 树形DP与数位DP
• 05-07 矩阵快速幂与线性递推

第六章 贪心

• 06-01 贪心策略与交换论证
• 06-02 区间调度与优化

第七章 字符串

• 07-01 字符串哈希详述
• 07-02 后缀数组

第八章 进阶

• 08-01 卷积与FFT
• 08-02 期望与概率
• 08-03 Zeta / Möbius 变换
• 08-04 计算几何基础
• 08-05 采样与随机化