分享丨滚动哈希详细讲解

113

14 小时前

10 小时前

发布于中国

一、引言
二、什么是滚动哈希？
三、多项式哈希
四、滚动公式
1. 1、增量滚动
2. 2、区间提取（前缀哈希）
五、模板
1. 1、选取 mod 和 base
2. 2、示例代码
六、降低哈希碰撞概率
七、常见坑点
八、滚动哈希解决什么问题？
九、总结

一、引言

「滚动哈希」可以说是解决字符串子串问题的神器，在算法竞赛与工程开发中都有着极高的实用价值。但想要真正吃透它的原理、边界条件与优化思路，其实并不简单。这篇帖子我会尽量用通俗直白的语言，从基础原理、实现细节、常见坑点到进阶应用，把整个滚动哈希体系完整讲一遍，不管是刚入门的新手，还是需要系统梳理的进阶选手，都能直接拿来学习和使用。

二、什么是滚动哈希？

滚动哈希 $^{=}$ 把字符串映射成一个数字（哈希值） $^{+}$ 在滑动窗口时 $O (1)$ 更新哈希值。

核心作用：

把字符串比较 $O (l e n)$ 降为数字比较 $O (1)$
配合滑动窗口，实现高效的子串处理

本质就是：用哈希值代替字符串本身做快速判断。

三、多项式哈希

把字符串看作一个 $ba se$ 进制数：

对字符串 $s [0.. n - 1]$ ，哈希定义为：

ha s h (s) = s [0] \cdot ba s e^{n - 1} + s [1] \cdot ba s e^{n - 2} + s [2] \cdot ba s e^{n - 3} + ... + s [n - 1]

为了避免溢出，通常取模一个大质数。

四、滚动公式

滚动哈希一般有两种滚动方式，分为增量滚动（在线查询）和区间提取（离线查询）。

1、增量滚动

适合一边遍历一边滚动的场景，比如：滑动窗口、逐字符扩展。

当我们已经知道字符串 $s [i .. j]$ 的哈希值 $h$ 时，就可以计算 $s [i .. j + 1]$ 与 $s [i + 1.. j]$ 的哈希值。

ha s h (s [i .. j + 1]) = h \cdot ba se + s [j + 1] ha s h (s [i + 1.. j]) = h - s [i] \cdot ba s e^{j - i}

2、区间提取（前缀哈希）

对于任意字符串 $s$ ，定义：

$h [i] = ha s h (s [0.. i - 1])$
$\text{pow_base}[i] = base^i$

递推公式：

\begin{aligned} \text{h}[i] &= \begin{cases}0 &\ i = 0\\ \text{h}[i - 1] \cdot base + \text{s}[i - 1] & \ i > 0 \end{cases}\\ \text{pow_base}[i] &= \begin{cases}1 &\ \ i = 0\\ \text{pow_base}[i - 1] \cdot base & \ \ i > 0 \end{cases} \end{aligned}

预处理之后，任意子串 $s [i .. j]$ 的哈希值就可以在 $O (1)$ 时间内被算出来。

hash(\text{s}[i..j]) = \text{h}[j + 1] - \text{h}[i] \cdot \text{pow_base}[j - i + 1]

注：结果为负数时，要把结果转为正数。

五、模板

1、选取 mod 和 base

一般情况下，选取两个互质的大质数作为 $m o d$ 和 $ba se$ 可以降低哈希冲突的概率。这里给大家推荐几个 $m o d$ 和 $ba se$ 。

base

mod

653
3359
9973

2、示例代码

C++

using ll = long long;
const ll base = 653;
const ll mod = 1000000009;

vector<ll> h, pow_base;

void init(const string &s) {
    int n = s.size();
    h.resize(n + 1);
    pow_base.resize(n + 1);
    pow_base[0] = 1;
    for (int i = 0; i < n; i++) {
        h[i+1] = (h[i] * base + s[i]) % mod;
        pow_base[i+1] = pow_base[i] * base % mod;
    }
}

ll get(int l, int r) {
    ll res = (h[r + 1] - h[l] * pow_base[r - l + 1]) % mod;
    if (res < 0) res += mod;
    return res;
}

六、降低哈希碰撞概率

一般情况下，单哈希的碰撞概率是较低的，但是在面对一些特殊用例的时候，他们也会碰撞。为了进一步降低碰撞概率，可以使用双哈希，甚至是三哈希。

另外， $ba se$ 和 $m o d$ 的大小、是否互质以及是否为质数等因素，都会影响哈希碰撞概率的高低。

七、常见坑点

1. 取模后出现负数

减法取模容易得到负数，必须判断并加上模数转为正数，否则哈希值错误。

2. 字符映射不当

尽量不要让字符值为 $0$ ，容易导致不同字符串哈希相同，建议统一偏移（如 s[i] - 'a' + 1 ）。

3. $\text{pow_base}$ 未预取模

指数增长极快，在不确定是否会溢出的情况下， $\text{pow_base}$ 每一步都要取模，否则导致结果错误。

4. $ba se$ 和 $m o d$ 选择不当

尽量使用大质数，且 $ba se < m o d$ 。二者不互质时会提升碰撞概率。

5. 单哈希被刻意卡数据

算法竞赛中，构造数据可以卡掉单哈希，稳妥做法是使用双哈希。

八、滚动哈希解决什么问题？

1、字符串匹配

求模式串 $p$ 在文本串 $s$ 中所有出现位置；
暴力 $O (n \cdot m)$ → 滚动哈希平均 $O (n + m)$ 。

例题：

28.找出字符串第一个匹配项的下标。滚动哈希模板题。

686. 重复叠加字符串匹配。

2、重复子串

滚动哈希判断是否存在重复子串。

例题：

1044. 最长重复子串。

187. 重复的DNA序列。

1392. 最长快乐前缀。

3、最长回文子串

预处理正哈希 $^{+}$ 逆哈希；
$O (1)$ 判断子串是否回文。

例题：

5. 最长回文子串。做到时间复杂度 $O (n lo g n)$ 。也可用 $Manacher$ 算法做到线性时间。

214. 最短回文串。做到线性时间复杂度。

647. 回文子串。做到时间复杂度 $O (n lo g n)$ 。也可用 $Manacher$ 算法做到线性时间。

4、统计不同子串数目

把所有子串哈希丢进一个集合，集合的大小即为答案。

例题：

1698. 字符串中不同整数的数目。

1316. 不同的循环子字符串。

5、字符串周期与前缀函数相关问题

快速判断周期、最小循环节。

例题：

459. 重复的子字符串。

796. 旋转字符串。

九、总结

「滚动哈希」凭借 $O (1)$ 提取子串哈希和 $O (1)$ 比较字符串的强大能力，成为处理字符串子串问题的通用利器。从基础的字符串匹配，到最长重复子串、最长回文子串、统计不同子串数目，再到字符串周期与前缀函数相关问题，都能以简洁的代码实现高效解法。

只要理解多项式哈希的本质，牢记滚动公式，避开常见坑点，就能在绝大多数字符串子串问题中做到思路清晰、代码简短、效率优秀。

希望这篇完整的滚动哈希讲解，能帮助你真正吃透这个算法，在做题与比赛中得心应手。

新春将至，也祝大家在新的一年里：
刷题全 $AC$ ，代码无 $Bug$ ，哈希不碰撞， $Offer$ 拿到手软！
万事顺意，马年大吉！