字符串哈希

前言

比较两个字符串是否相同，朴素方法是逐字符比较，$O(\text{长度})$。但如果要比较 $10^5$ 次子串呢？每次最长 $10^5$ 个字符——总时间 $10^{10}$，太慢了。

字符串哈希（String Hashing / Rolling Hash）的思路极其巧妙：把字符串映射成一个整数。如果两个字符串的哈希值相同，它们大概率是相同的字符串（有极小概率冲突，但竞赛中通常可以忽略）。

核心技巧：用前缀哈希 + 前缀和的方法，在 $O(1)$ 时间内算出任意子串的哈希值。预处理 $O(n)$，每次查询 $O(1)$。

问题的本质

把字符串变成多项式

选一个基数 $B$ 和模数 $M$（通常 $M = 2^{64}$，用 unsigned long long 自然溢出）。字符串 $S = s_1 s_2 \ldots s_n$ 的哈希值为：

$H(S) = s_1 \cdot B^{n-1} + s_2 \cdot B^{n-2} + \cdots + s_n \cdot B^0 \pmod{M}$

这就像把字符串当成一个 $B$ 进制的数。不同的字符串（大概率）对应不同的数。

前缀哈希：O(1) 子串查询

关键洞察：预处理前缀哈希 $h[i] = s_1 B^{i-1} + s_2 B^{i-2} + \cdots + s_i B^0$。那么子串 $S[l..r]$ 的哈希值为：

$\text{hash}(l, r) = h[r] - h[l-1] \cdot B^{r-l+1}$

类比前缀和：子串的和 = 后缀前缀和 - 前缀前缀和（再乘以适当的 $B$ 的幂来对齐位数）。

为什么哈希冲突概率极低？

用 unsigned long long 自然溢出（模 $2^{64}$），基数选 131 或 911382629。两个不同字符串哈希相同的概率约 $1/2^{64}$，即 $5 \times 10^{-20}$。竞赛中几乎不会遇到冲突。

理论 + 代码

前缀哈希预处理

#include <cstdio>
using namespace std;

typedef unsigned long long ull;
const ull B = 131;  // ① 基数，通常选质数

ull h[MAXN], pw[MAXN]; // h[i]=前缀哈希, pw[i]=B^i

void build(const char* s, int n) {
    pw[0] = 1;
    for (int i = 1; i <= n; i++) pw[i] = pw[i-1] * B; // ② 预计算 B 的幂
    h[0] = 0;
    for (int i = 1; i <= n; i++)
        h[i] = h[i-1] * B + s[i-1]; // ③ 递推前缀哈希
}

ull getHash(int l, int r) { // 1-indexed, 闭区间 [l, r]
    return h[r] - h[l-1] * pw[r - l + 1]; // ④ O(1) 子串哈希
}

逐行解析：

• ① 基数 $B$ 选一个比字符集大的质数（小写字母 26 个，$B=131$ 足够）。
• ② pw[i] = B^i，用于查询时对齐位数。
• ③ 递推：$h[i] = h[i-1] \cdot B + s_i$。每多一个字符，旧的哈希值左移一位（乘 $B$），加上新字符。
• ④ h[r] - h[l-1] * pw[r-l+1]：类比前缀和，但需要对齐位数。

模拟走一遍

$S = \text{"abcbabc"}$，$B = 131$（简化用小数演示）：

i	s[i]	h[i]	说明
0	-	0	初始
1	’a’=97	97	0×131+97
2	’b’=98	97×131+98 = 12805
3	’c’=99	12805×131+99 = 1677464

查询 S[1,3]=“abc” 的哈希 = h[3] - h[0]×pw[3] = 1677464 - 0 = 1677464。

回文判断

回文 = 正着读和反着读一样。所以：

• 预处理正串哈希和反串哈希
• 子串 $S[l..r]$ 是回文 ⟺ 正串哈希 == 反串哈希

例题

例题 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

分析：裸的字符串哈希模板题。预处理前缀哈希，每次查询 $O(1)$ 比较两个子串的哈希值。

代码：

#include <cstdio>
using namespace std;

typedef unsigned long long ull;
const int MAXN = 200006;
const ull B = 131;

ull h[MAXN], pw[MAXN];

void build(const char* s, int n) {
    pw[0] = 1;
    for (int i = 1; i <= n; i++) pw[i] = pw[i-1] * B;
    h[0] = 0;
    for (int i = 1; i <= n; i++) h[i] = h[i-1] * B + s[i-1];
}

ull getHash(int l, int r) {
    return h[r] - h[l-1] * pw[r - l + 1];
}

int main() {
    int N, Q;
    char S[MAXN];
    scanf("%d%d", &N, &Q);
    scanf("%s", S);
    build(S, N);
    while (Q--) {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        printf("%s\n", getHash(a, b) == getHash(c, d) ? "Yes" : "No");
    }
    return 0;
}

逐行解析：

• build 预处理前缀哈希和 $B$ 的幂。
• getHash(l, r) $O(1)$ 计算子串哈希。
• 比较两个子串的哈希值，相同则”大概率”字符串相同。

验证：$S=\text{"abcbabc"}$。$S[1,3]$=“abc” vs $S[5,7]$=“abc”→Yes。$S[1,5]$=“abcba” vs $S[2,6]$=“bcbab”→No。✓

---

例题 2：TB B56 — Palindrome Queries

题目：长度 $N$ 的字符串 $S$。$Q$ 个查询：子串 $S[L_i..R_i]$ 是否是回文？

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

—— AtCoder Tessoku Book B56

分析：预处理正串和反串的哈希。子串是回文 ⟺ 正串 $[L, R]$ 的哈希 = 反串 $[N-R+1, N-L+1]$ 的哈希。

代码：

#include <cstdio>
using namespace std;

typedef unsigned long long ull;
const int MAXN = 100006;
const ull B = 131;

ull h[MAXN], rh[MAXN], pw[MAXN];
char S[MAXN], rS[MAXN];

void build(int n) {
    pw[0] = 1;
    for (int i = 1; i <= n; i++) pw[i] = pw[i-1] * B;
    h[0] = rh[0] = 0;
    for (int i = 1; i <= n; i++) {
        h[i] = h[i-1] * B + S[i-1];      // ① 正串哈希
        rh[i] = rh[i-1] * B + rS[i-1];    // ② 反串哈希
    }
}

ull getHash(ull h[], int l, int r) {
    return h[r] - h[l-1] * pw[r - l + 1];
}

int main() {
    int N, Q;
    scanf("%d%d", &N, &Q);
    scanf("%s", S);
    for (int i = 0; i < N; i++) rS[i] = S[N-1-i]; // ③ 构造反串
    build(N);
    while (Q--) {
        int L, R;
        scanf("%d%d", &L, &R);
        int rL = N - R + 1, rR = N - L + 1; // ④ 反串中的对应区间
        printf("%s\n", getHash(h, L, R) == getHash(rh, rL, rR) ? "Yes" : "No");
    }
    return 0;
}

逐行解析：

• ③ 反转字符串 $S$ 得到 $rS$。
• ④ 正串 $[L, R]$ 在反串中对应 $[N-R+1, N-L+1]$。例如正串 $[1,4]$（长度 4）对应反串 $[N-3, N]$。
• 比较正串和反串对应区间的哈希值，相同则是回文。

验证：$S=\text{"mississippi"}$。$S[5,8]$=“issi”，反串=“ippississim”，对应 $[4,7]$=“issi”。哈希相等 → Yes。✓

---

例题 3（练习）：T90 047 — Monochromatic Diagonal（★7）

题目：两个由 ‘R’,‘G’,‘B’ 组成的字符串 $S, T$（长度 $N$）。构造 $N \times N$ 矩阵，其中 $(i,j)$ 的颜色由 $s_i$ 和 $t_j$ 决定。求有多少条对角线（左上到右下）是单色的。

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

—— AtCoder Typical 90 047

思路提示：★7 难题。关键观察：对角线 $(i,j)$ 上所有格子 $s_{i+k}$ 和 $t_{j+k}$ 的颜色由某种规则确定。通过字符串哈希可以高效判断同一对角线上所有位置的颜色是否一致。

参考文献

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

• 8.6 B56 Palindrome Queries（字符串哈希+回文判定 解说，含完整哈希实现）

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

• A56 String Hash（字符串哈希基础）【例题】
• B56 Palindrome Queries（回文查询）【例题】

实战练习 — 競プロ典型 90 問

• 047 Monochromatic Diagonal（★7，哈希应用）【例题】

---

系列索引

第零章 基础工具

• 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 采样与随机化