教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文基于 AlgoNote 仓库 docs/04_string/04_03_string_rabin_karp.md 整理。Rabin KarpRK算法由 Michael Oser Rabin 与 Richard Manning Karp 于 1987 年提出是一种利用哈希快速筛查匹配起点的单模式串匹配算法先计算模式串的哈希值再借助「滚动哈希」在 O(1) 时间内更新文本中相邻子串的哈希仅当哈希相等时才逐字符核验。读完本文你将掌握 RK 的完整推导过程、可运行的 Python 实现、哈希参数选取原则以及它在 LeetCode 题目含反向滚动哈希题 2156中的实战用法。1. RK 算法核心思想与定位在字符串匹配问题中文本串 $T$ 长度为 $n$模式串 $p$ 长度为 $m$目标是在 $T$ 中找出所有与 $p$ 相同的连续子串即 $p$ 的出现位置。朴素 Brute ForceBF算法要对每个可能的起点做最长 $m$ 次逐字符比较总复杂度为 $O(n \times m)$存在大量无效比较参见仓库 BF 算法文档。RK 算法的突破口是用哈希代替逐字符比较先计算模式串 $p$ 的哈希值 $H(p)$对文本串 $T$ 的所有长度为 $m$ 的子串 $T_{[i, im-1]}$ 计算哈希 $H(T_{[i, im-1]})$哈希不等则直接跳过该起点哈希相等时才逐字符比对以排除「哈希冲突」不同子串哈希恰好相同造成的误判。关键点在于第 2 步如果每个子串哈希都从头算起代价是 $O(nm)$毫无优势。RK 的高明之处是引入滚动哈希Rolling Hash让相邻子串的哈希能在 O(1) 时间内由上一个子串推导而来从而把整体平均复杂度降到 O(n)。从 04_01_string_basic.md 的算法梳理看RK 属于「基于子串搜索的方法」平均时间复杂度 $O(nm)$、空间复杂度 $O(1)$、使用滚动哈希、适合需要处理多个模式串或对哈希冲突不敏感的场景是单模式串匹配算法家族BF / KMP / BM / Horspool / Sunday / RK中的重要一员。2. RK 算法整体流程设 $n|T|$、$m|p|$RK 算法的完整步骤如下计算模式串哈希 $H(p)$计算文本串首个长度为 $m$ 的子串 $T_{[0,m-1]}$ 的哈希 $H(T_{[0,m-1]})$用滚动哈希依次得到其余 $n-m$ 个相邻子串的哈希每一步 O(1)逐一比较 $H(T_{[i,im-1]})$ 与 $H(p)$不相等跳过该起点相等逐字符核验若完全相同则返回起点 $i$否则继续全部位置检查完毕后仍未匹配返回 $-1$。3. 滚动哈希把子串看作 d 进制多项式滚动哈希采用Rabin fingerprint思想把子串视作 $d$ 进制多项式$d$ 为字符集大小基于上一个子串的哈希在 O(1) 时间得到下一个子串的哈希。3.1 直观例子26 进制下的 cat假设字符串只包含 $a \sim z$ 这 26 个小写字母即可用 26 进制数表示一个字符串映射规则为字符abc...t...z数值012...19...25cat的哈希可表示为$$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_{k0}^{m-1} p_k, d^{m-1-k}$文本首子串$H(T_{[0,m-1]})\sum\limits_{k0}^{m-1} T_k, d^{m-1-k}$滚动关系$H(T_{[i1,im]})\big(H(T_{[i,im-1]})-T_i, d^{m-1}\big), dT_{im}$。其中 $d^{m-1}$ 是「最高位字符」对应的权值滚动更新时需要预先算好用于移除当前子串最左侧的字符。4. 哈希参数基数 d 与模数 q 的选取为避免溢出并降低冲突概率实际计算中通常对大质数 $q$ 取模模数宜大且为质数基数 d通常取大于字符集大小的数。仓库实现中示例取 $d256$对应 ASCII 字符集范围可将每个字符映射为 0~255 的编码若只处理 26 个小写字母取 $d26$ 即可。模数 q取一个较大的质数如 $10^97$、$10^99$。取质数的原因是质数模数能降低不同字符串哈希碰撞的概率模数越大哈希值空间越大碰撞概率越低。取模运算性质滚动更新依赖两条基本性质——$(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 -15.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源码版与文档版的差异源码版未显式处理空模式串$m0$分支。此时内层核验循环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做了多组用例实测基数 $d256$、模数 $q101$用例期望结果实测结果Thello world hellopworld66Taaaaapbba-1-1Tabcp空模式00Tabcpabcd文本短于模式-1-1构造哈希冲突用例超长全a前缀-1-1实测输出与预期一致说明滚动哈希更新、冲突核验、边界判断等环节在 $d$、$q$ 取值下的行为均符合算法设计。6. 复杂度与性质分析指标复杂度说明最好时间复杂度$O(n-m1)$无哈希冲突时仅需 $n-m1$ 次哈希对比均为 O(1)无需逐字符校验最坏时间复杂度$O(m(n-m1))\approx O(nm)$每次哈希均冲突需 $n-m1$ 次逐字符全量比对每次 O(m)平均时间复杂度$O(n-m1)$期望哈希冲突极少绝大多数位置仅哈希对比均摊 O(1)空间复杂度O(1)仅需常数变量存储哈希值与辅助参数与 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[i1]) \times p^1 \dots val(s[ik-1]) \times p^{k-1}) \bmod m$RK 公式$hash(s,p,m) (val(s[i]) \times p^{k-1} val(s[i1]) \times p^{k-2} \dots val(s[ik-1]) \times p^0) \bmod m$。由于公式方向相反正向滚动时移除最左侧字符需要「除以 $p$」而除法不满足取模运算的分配律会导致结果错误。解法是从右向左逆向遍历移除最右侧字符减去 $val(s[ik-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 在单模式串匹配家族中的位置如下算法预处理时间匹配时间空间复杂度特点Brute ForceO(1)$O(n \times m)$O(1)简单直观Rabin KarpO(m)平均 O(n)最坏 $O(n \times m)$O(1)滚动哈希KMPO(m)O(n)O(m)利用失配信息稳定线性Boyer Moore$O(mk)$平均 O(n/m)最坏 $O(n \times m)$O(k)启发式跳跃从右向左Horspool$O(mk)$平均 O(n)最坏 $O(n \times m)$O(k)BM 简化版Sunday$O(mk)$平均 O(n)最坏 $O(n \times m)$O(k)从左到右跳跃能力强选型建议追求最坏情况也线性用 KMP模式串长、字符集小用 BM 系BM/Horspool/Sunday需要多模式比对或哈希化处理用 RK模式很短或一次性匹配用 BF 即可。9. 总结Rabin KarpRK算法将模式串与文本子串转化为哈希值利用「滚动哈希」在 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赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐哈希算法实战指南从Rabin-Karp到Java哈希表应用哈希算法实战指南从Rabin Karp到Java哈希表应用 在数据处理和算法设计中哈希Hash技术是提升效率的核心武器。无论是字符串搜索、数据去重还是快示例工程算法10个必用的UIkit核心组件清单按钮、表单、导航栏与模态框一网打尽10个必用的UIkit核心组件清单按钮、表单、导航栏与模态框一网打尽 UIkit 是一款轻量且模块化的前端框架front end framework用于前端UI组件Rabin-Karp 字符串搜索算法基于哈希滑窗的 Swift 实现与实战解析Rabin Karp 字符串搜索算法基于哈希滑窗的 Swift 实现与实战解析 Rabin Karp 是一种利用滚动哈希rolling hash加速多模式示例工程教程上一篇Pysolr开发贡献如何参与这个顶级Python Solr客户端项目下一篇java2python实现跨语言转换的自动化工具含3个实战技巧创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
