Rabin–Karp 算法 | Codeboy's Blog

形式陈述

Rabin–Karp 为模式 $P$ 和文本每个长度 $m$ 窗口计算可滚动更新的模多项式指纹。指纹不等时必不匹配；相等时必须逐字符核验，或接受受控的随机碰撞概率。使用随机模数或随机基数时，对固定不等字符串可给小碰撞概率，期望时间常为 $O(n+m)$ ，最坏核验可达 $O(nm)$ 。

直觉

Rabin–Karp 把固定长度的字符串窗口映成可滚动更新的便宜数字指纹，用来快速排除绝大多数窗口。窗口右移时减去最高位贡献、乘基数并加入新字符，因而每步常数时间；哈希相等只产生候选匹配，仅对这些位置做昂贵的最终字符比较来排除碰撞。随机选择模数或基数可让对抗碰撞概率可控。

Rabin–Karp 滚动更新窗口哈希并对哈希命中候选逐字符核验 — 滚动指纹、候选与字符核验

例子与边界

窗口右移时从旧哈希减去最高位贡献、乘基数并加新字符。模运算滚动指纹不是密码哈希，也不需要抗主动碰撞；反之，通用密码哈希通常不支持 $O(1)$ 滚动更新。若不做核验，算法是 Monte Carlo；核验后正确性确定但运行时间随机或输入相关。

以基 $B$ 、模 $p$ 表示窗口 $s_0\ldots s_{m-1}$ 的哈希。右移一位时先减 $s_0B^{m-1}$ ，再乘 $B$ 、加新字符并取模。文本 abracadabra 搜 abra 时，首窗命中，后续滚动到末尾再次命中。

若哈希命中后不核验原串，算法成为 Monte Carlo 并可能假阳性；固定弱参数可被构造大量碰撞，使验证退化为 $O(nm)$ 。负模结果、整数溢出和字符编码也需在实现中统一。

推论与应用

字符串匹配是任务，模同余支撑滚动更新，随机化提供碰撞概率分析。通用哈希给出“对任意固定不同键，随机选函数后碰撞概率小”的族性质；滚动多项式指纹还要求窗口能在 $O(1)$ 时间删首添尾，不能把任意通用族直接换进公式。Rabin–Karp 因而适合同长多模式、二维窗口、重复块筛选和文档片段指纹；最后一种仍需把“快速发现候选相似块”与“抗篡改的密码学摘要”分开。

它仍是顺序扫描一次文本的候选过滤器。若文本固定、模式查询很多，FM-index会预处理 BWT 与 rank 结构，以压缩空间回答 count，并为定位另付采样成本。双模数只能降低工程碰撞概率，不等于这种静态全文索引，也不能替代对随机参数和核验策略的正式说明。

参考资料

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。
Dan Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997，Chs. 1–8。

形式陈述 ​

反向链接

形式陈述