企业官网建设流程全解析

• 教程
• 文档
• 知识库

本文基于 AlgoNote 仓库 docs/04_string/04_03_string_rabin_karp.md 整理。Rabin Karp（RK）算法由 Michael Oser Rabin 与 Richard Manning Karp 于 1987 年提出，是一种利用哈希快速筛查匹配起点的单模式串匹配算法：先计算模式串的哈希值，再借助「滚动哈希」在 O(1) 时间内更新文本中相邻子串的哈希，仅当哈希相等时才逐字符核验。读完本文你将掌握 RK 的完整推导过程、可运行的 Python 实现、哈希参数选取原则，以及它在 LeetCode 题目（含反向滚动哈希题 2156）中的实战用法。

1. RK 算法核心思想与定位

在字符串匹配问题中，文本串 $T$ 长度为 $n$，模式串 $p$ 长度为 $m$，目标是在 $T$ 中找出所有与 $p$ 相同的连续子串（即 $p$ 的出现位置）。朴素 Brute Force（BF）算法要对每个可能的起点做最长 $m$ 次逐字符比较，总复杂度为 $O(n \times m)$，存在大量无效比较（参见仓库 BF 算法文档）。

RK 算法的突破口是用哈希代替逐字符比较：

1. 先计算模式串 $p$ 的哈希值 $H(p)$；
2. 对文本串 $T$ 的所有长度为 $m$ 的子串 $T_{[i, i+m-1]}$ 计算哈希 $H(T_{[i, i+m-1]})$；
3. 哈希不等则直接跳过该起点；哈希相等时才逐字符比对，以排除「哈希冲突」（不同子串哈希恰好相同）造成的误判。

关键点在于第 2 步：如果每个子串哈希都从头算起，代价是 $O(nm)$，毫无优势。RK 的高明之处是引入滚动哈希（Rolling Hash），让相邻子串的哈希能在 O(1) 时间内由上一个子串推导而来，从而把整体平均复杂度降到 O(n)。

从 04_01_string_basic.md 的算法梳理看，RK 属于「基于子串搜索的方法」：平均时间复杂度 $O(n+m)$、空间复杂度 $O(1)$、使用滚动哈希、适合需要处理多个模式串或对哈希冲突不敏感的场景，是单模式串匹配算法家族（BF / KMP / BM / Horspool / Sunday / RK）中的重要一员。

2. RK 算法整体流程

设 $n=|T|$、$m=|p|$，RK 算法的完整步骤如下：

1. 计算模式串哈希 $H(p)$；
2. 计算文本串首个长度为 $m$ 的子串 $T_{[0,m-1]}$ 的哈希 $H(T_{[0,m-1]})$；
3. 用滚动哈希依次得到其余 $n-m$ 个相邻子串的哈希，每一步 O(1)；
4. 逐一比较 $H(T_{[i,i+m-1]})$ 与 $H(p)$：
   • 不相等：跳过该起点；
   • 相等：逐字符核验，若完全相同则返回起点 $i$，否则继续；
5. 全部位置检查完毕后仍未匹配，返回 $-1$。

3. 滚动哈希：把子串看作 d 进制多项式

滚动哈希采用Rabin fingerprint思想：把子串视作 $d$ 进制多项式（$d$ 为字符集大小），基于上一个子串的哈希在 O(1) 时间得到下一个子串的哈希。

3.1 直观例子：26 进制下的 "cat"

假设字符串只包含 $a \sim z$ 这 26 个小写字母，即可用 26 进制数表示一个字符串，映射规则为：

"cat"的哈希可表示为：

$$Hash(cat) = c \times 26^2 + a \times 26^1 + t \times 26^0 = 2 \times 26^2 + 0 \times 26^1 + 19 \times 26^0 = 1371$$

3.2 相邻子串的 O(1) 更新

如果"cat"的相邻子串为"ate"，直接计算：

$$Hash(ate) = a \times 26^2 + t \times 26^1 + e \times 26^0 = 0 \times 26^2 + 19 \times 26^1 + 4 \times 26^0 = 498$$

而利用上一个子串"cat"的哈希滚动更新：

$$Hash(ate) = (Hash(cat) - c \times 26^2) \times 26 + e \times 26^0 = (1371 - 2 \times 26^2) \times 26 + 4 \times 26^0 = 498$$

两种方式计算结果一致，但第二种不需要重新遍历子串，只需一次减法、一次乘法、一次加法即可完成，单次子串哈希更新的时间复杂度降为 O(1)。直观理解：先把最左侧字符的贡献（$c \times 26^2$）减掉，相当于把整个数向左平移一位（乘 26），再把新字符 $e$ 追加到最低位。

3.3 形式化定义

给定文本串 $T$ 与模式串 $p$，设 $n=|T|$、$m=|p|$、字符集大小为 $d$，则：

• 模式串：$H(p)=\sum\limits_{k=0}^{m-1} p_k, d^{m-1-k}$；
• 文本首子串：$H(T_{[0,m-1]})=\sum\limits_{k=0}^{m-1} T_k, d^{m-1-k}$；
• 滚动关系：$H(T_{[i+1,i+m]})=\big(H(T_{[i,i+m-1]})-T_i, d^{m-1}\big), d+T_{i+m}$。

其中 $d^{m-1}$ 是「最高位字符」对应的权值，滚动更新时需要预先算好，用于移除当前子串最左侧的字符。

4. 哈希参数：基数 d 与模数 q 的选取

为避免溢出并降低冲突概率，实际计算中通常对大质数 $q$ 取模（模数宜大且为质数）：

• 基数 d：通常取大于字符集大小的数。仓库实现中示例取 $d=256$（对应 ASCII 字符集范围），可将每个字符映射为 0~255 的编码；若只处理 26 个小写字母，取 $d=26$ 即可。
• 模数 q：取一个较大的质数，如 $10^9+7$、$10^9+9$。取质数的原因是质数模数能降低不同字符串哈希碰撞的概率；模数越大，哈希值空间越大，碰撞概率越低。
• 取模运算性质：滚动更新依赖两条基本性质——$(a \times b) \bmod m = ((a \bmod m) \times (b \bmod m)) \bmod m$ 与 $(a + b) \bmod m = (a \bmod m + b \bmod m) \bmod m$。这保证滚动过程中「先取模再运算」与「先运算再取模」结果一致，从而可以把每一步结果都压缩在 $[0, q)$ 内。
• 负值处理：减去最高位字符贡献后哈希可能变为负数，Python 的%运算符对负数会返回非负余数，但为可读性与跨语言移植，仓库实现中还显式执行了hash_t = (hash_t + q) % q确保哈希值非负。
• 幂次计算：$d^{m-1}$ 若用普通幂运算可能中间溢出，应使用 Python 的pow(d, m - 1, q)三参形式直接计算模幂，这正是文档与仓库实现共同采用的做法。

5. 代码实现：文档版与仓库源码对照

5.1 文档给出的标准实现

以下为 04_03_string_rabin_karp.md 中的完整实现，已对边界情况（空模式串、文本短于模式）做了显式处理：

# T: 文本串，p: 模式串，d: 字符集大小（基数），q: 模数（质数） def rabinKarp(T: str, p: str, d: int, q: int) -> int: n, m = len(T), len(p) if m == 0: return 0 if n < m: return -1 hash_p, hash_t = 0, 0 # 计算 H(p) 与首个子串的哈希 for i in range(m): hash_p = (hash_p * d + ord(p[i])) % q hash_t = (hash_t * d + ord(T[i])) % q # 使用 pow 的三参形式避免中间溢出 power = pow(d, m - 1, q) # d^(m-1) % q，用于移除最高位字符 for i in range(n - m + 1): if hash_p == hash_t: # 避免冲突：逐字符核验 match = True for j in range(m): if T[i + j] != p[j]: match = False break if match: return i if i < n - m: # 滚动更新到下一个子串 hash_t = (hash_t - power * ord(T[i])) % q # 去掉最高位字符 hash_t = (hash_t * d + ord(T[i + m])) % q # 加入新字符 return -1

5.2 仓库源码实现与差异

仓库配套源码位于 string_rabin_karp.py，核心逻辑与文档版一致，差异点在于：

# T 为文本串，p 为模式串，d 为字符集的字符种类数，q 为质数 def rabinKarp(T: str, p: str, d, q) -> int: n, m = len(T), len(p) if n < m: return -1 hash_p, hash_t = 0, 0 for i in range(m): hash_p = (hash_p * d + ord(p[i])) % q # 计算模式串 p 的哈希值 hash_t = (hash_t * d + ord(T[i])) % q # 计算文本串 T 中第一个子串的哈希值 power = pow(d, m - 1) % q # power 用于移除字符哈希时 for i in range(n - m + 1): if hash_p == hash_t: # 检查模式串 p 的哈希值和子串的哈希值 match = True # 如果哈希值相等，验证模式串和子串每个字符是否完全相同（避免哈希冲突） for j in range(m): if T[i + j] != p[j]: match = False # 模式串和子串某个字符不相等，验证失败，跳出循环 break if match: # 如果模式串和子串每个字符是否完全相同，返回匹配开始位置 return i if i < n - m: # 计算下一个相邻子串的哈希值 hash_t = (hash_t - power * ord(T[i])) % q # 移除字符 T[i] hash_t = (hash_t * d + ord(T[i + m])) % q # 增加字符 T[i + m] hash_t = (hash_t + q) % q # 确保 hash_t >= 0 return -1

源码版与文档版的差异：

• 源码版未显式处理空模式串（$m=0$）分支。此时内层核验循环range(0)天然空转、match恒为True，首个起点即返回 0，行为上恰好等价于「空串匹配返回 0」，但文档版显式写出if m == 0: return 0更为清晰严谨；
• 源码版在滚动更新后额外执行hash_t = (hash_t + q) % q，显式保证哈希值非负，增强了实现的健壮性与可移植性；
• 源码版文件末尾自带一行测试调用print(rabinKarp("aaaaa", "bba", 256, 101))，执行结果为-1（模式串"bba"不出现在"aaaaa"中），可直接运行该文件验证。

运行方式：在仓库根目录执行python3 codes/python/04_string/string_rabin_karp.py即可看到输出；若需导入复用，可import该模块后自行构造文本串与模式串测试。

5.3 运行验证

为验证算法正确性，对仓库源码版rabinKarp做了多组用例实测（基数 $d=256$、模数 $q=101$）：

实测输出与预期一致，说明滚动哈希更新、冲突核验、边界判断等环节在 $d$、$q$ 取值下的行为均符合算法设计。

6. 复杂度与性质分析

与 BF 算法相比，RK 通过哈希筛选把大多数不匹配位置在 O(1) 内排除；但哈希冲突会触发逐字符校验，致使最坏复杂度退化。这说明哈希参数的选取直接决定算法实际表现：基数 $d$ 与模数 $q$ 选择得当，冲突概率极低，平均性能接近线性；选择不当（如 $q$ 过小或为合数），冲突频发，可能退化为 O(nm)。

优点：

• 滚动哈希使子串哈希更新为 O(1)，平均性能优于 BF；
• 易于扩展到多模式串场景（统一维护多个模式串的哈希，一次遍历文本即可比对多个模式）。

缺点：

• 存在哈希冲突，最坏复杂度可退化至 O(nm)；
• 需合理选择基数 $d$ 与大质数模 $q$，以降低冲突概率。

7. 实战应用：RK 思想的三种变体

7.1 LeetCode 0028：字符串匹配标准场景

0028. 找出字符串中第一个匹配项的下标 是字符串匹配经典题，其题解中给出的 RK 版实现使用 Python 内建hash()函数直接计算子串哈希，逻辑更简洁，但原理一致：先求模式串哈希，再对每个起点比对哈希，相等时逐字符确认。

7.2 LeetCode 2156：反向滚动哈希（除法陷阱）

2156. 查找给定哈希值的子串（困难）是 RK 滚动哈希思想的直接延伸，但哈希公式与 RK 恰好相反：

• 本题公式：$hash(s,p,m) = (val(s[i]) \times p^0 + val(s[i+1]) \times p^1 + \dots + val(s[i+k-1]) \times p^{k-1}) \bmod m$；
• RK 公式：$hash(s,p,m) = (val(s[i]) \times p^{k-1} + val(s[i+1]) \times p^{k-2} + \dots + val(s[i+k-1]) \times p^0) \bmod m$。

由于公式方向相反，正向滚动时移除最左侧字符需要「除以 $p$」，而除法不满足取模运算的分配律，会导致结果错误。解法是从右向左逆向遍历：移除最右侧字符（减去 $val(s[i+k-1]) \times p^{k-1}$）、整体乘 $p$、移入最左侧字符 $val(s[i-1])$，全程只用乘法与取模，数学上完全合法。这一题深刻展示了「滚动哈希的更新方向必须与哈希多项式的权重方向一致」这一易错点。

7.3 多模式串匹配

RK 天然适合多模式串场景：预处理时统一维护 $r$ 个模式串的哈希（O(mr) 代价），随后对文本的每个子串只算一次哈希，与 $r$ 个模式哈希逐一比对（O(1) 每次），总代价从朴素方案的 O(nmr) 降为 O(nr)。这是它在 04_01_string_basic.md 中被归类为「哈希与子串搜索类方法」并推荐用于多模式比对的原因；不过当模式串数量很大时，AC 自动机等专用多模式算法通常是更优选择。

7.4 更广阔的应用场景

滚动哈希不止用于字符串匹配：

• 内容指纹/重复检测：对文档、代码文件计算滚动哈希，可快速定位相似片段（类似 Rabin fingerprint 的经典用途）；
• 文件分块去重：利用滚动哈希在数据流中确定分块边界；
• 滑动窗口类算法题：凡是要对「所有定长子串」做统计或比较的题目，滚动哈希都能将单次子串计算从 O(m) 降到 O(1)。

8. 与常见单模式串匹配算法对比

结合 04_01_string_basic.md 的算法梳理，RK 在单模式串匹配家族中的位置如下：

选型建议：追求最坏情况也线性用 KMP；模式串长、字符集小用 BM 系（BM/Horspool/Sunday）；需要多模式比对或哈希化处理用 RK；模式很短或一次性匹配用 BF 即可。

9. 总结

Rabin Karp（RK）算法将模式串与文本子串转化为哈希值，利用「滚动哈希」在 O(1) 时间完成相邻子串哈希的更新，从而以平均 O(n) 的代价快速筛查匹配位置，大幅减少无效字符比较；哈希冲突时回退逐字符比对，最坏情况下复杂度与朴素法相同。其核心收益来自两点：哈希筛选把大多数不匹配位置在 O(1) 内排除，滚动更新让每个子串哈希不再从零计算。合理选择基数 $d$ 与大质数模 $q$ 可有效降低冲突概率，而滚动方向与哈希权重方向的一致性（见 2156 题）则是工程实现中最易踩坑之处。RK 是一种高效且易于扩展（多模式、指纹类应用）的字符串匹配算法。

练习题目

以下题目来自 单模式串匹配题目列表，均可用 RK / 滚动哈希思路求解：

• 0028. 找出字符串中第一个匹配项的下标
• 0459. 重复的子字符串
• 0686. 重复叠加字符串匹配
• 0796. 旋转字符串
• 1408. 数组中的字符串匹配
• 2156. 查找给定哈希值的子串（困难，反向滚动哈希）

参考资料

• 【书籍】数据结构与算法 Python 语言描述 - 裘宗燕 著
• 【文章】字符串匹配基础（上）- 数据结构与算法之美 - 极客时间
• 【文章】字符串匹配算法 - Rabin Karp 算法 - coolcao 的小站
• 【问答】Python: Rabin-Karp algorithm hashing - Stack Overflow

• 教程
• 文档
• 知识库