字符串哈希 · CSP-S 知识点详解

一、要解决的问题

字符串题里最常见的原子问题是："子串 A 和子串 B 相等吗？"逐字符比较是 O(长度)，在"比较次数很多"的题目里（回文判断、LCP、循环节）会成为瓶颈。字符串哈希预处理 O(n) 之后，每次比较只要 O(1)。

生活类比：图书馆给每本书编一个索书号。想知道两本书是不是同一本，不用逐页对比——对一下索书号就行。哈希值就是子串的"索书号"：号相同几乎必然内容相同。

二、多项式滚动哈希

把字符串看成 B 进制数，前缀哈希递推：

h[0] = 0；h[i] = h[i−1] × B + code(s[i]) （code 把字符映射为非零整数，如 s[i] − 'a' + 1）
子串 s[l..r] 的哈希 = h[r] − h[l−1] × B^r−l+1

前缀哈希：每个前缀是一个 B 进制数，子串哈希 = 高位做差

三、三个高频应用

① O(1) 判断两个子串是否相等

哈希相等即视为相等。配合二分长度可求两个后缀的 LCP（最长公共前缀），O(log n) 每次。

② O(1) 判断子串是否回文

对原串和反转串各建一份哈希：s[l..r] 是回文 ⇔ 原串该段哈希 = 反串对应段哈希（注意下标镜像换算）。与 Manacher 互补：哈希写法短、能答任意区间询问；Manacher 一次求出所有中心。

回文判定：一段正着读和倒着读的"指纹"相同

③ 循环节 / 周期判断

s 有长度 k 的循环节 ⇔ s[1..n−k] 的哈希 = s[k+1..n] 的哈希，一次哈希比较代替逐位验证。

四、模板代码

typedef unsigned long long ull;
const int N = 1e6 + 10;
const ull B = 131;                    // 或 13331，常用质数进制
ull h[N], p[N];
void init(const char *s, int n) {     // s 从 1 开始存
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        p[i] = p[i-1] * B;
        h[i] = h[i-1] * B + (s[i] - 'a' + 1);
    }
}
ull get(int l, int r) { return h[r] - h[l-1] * p[r-l+1]; }

用 unsigned long long 自然溢出相当于模 2⁶⁴，省去取模运算；担心被卡可换双模（两个 10⁹ 级质数分别取模）。

五、易错点清单

字符映射要 +1：'a' → 0 会让 "a"、"aa" 哈希相同（前导零丢失）。
进制 B 要大于字符集大小，常用 131 / 13331；太小易冲突。
反串下标换算：原串 s[l..r] 在反串中对应 [n−r+1, n−l+1]，写错就全盘皆输。
哈希是"几乎必然正确"，评测若有 anti-hash 数据就用双模或改用确定性算法。

六、练习

P3370【模板】字符串哈希
回文判断：与 Manacher 对照练习；进阶组合"回文划分计数"（哈希 O(n²) DP 或 Eertree O(n)）
真题对照：CSP-S 2024 T3 染色、2025 T3 谐音替换（字符串题近两年强势，哈希是保底分利器）