形式陈述

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

直觉

先用便宜的数字指纹快速排除绝大多数窗口，只对指纹碰巧相同的位置做昂贵的精确比较。

例子与边界

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

推论与应用

Rabin–Karp 适合多模式同长度搜索、重复检测、文档指纹和二维模式匹配。

参考资料

• 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。