Rabin-Karp 算法

定义

Rabin-Karp 算法由 Michael Rabin 与 Richard Karp 于 1987 年提出,通过比较哈希值而非逐字符比较来查找模式串。

原理

将模式串的哈希值与文本中每个等长窗口的哈希值比较,哈希相等时再逐字符验证以排除碰撞。关键技术是滚动哈希(rolling hash):把字符串视为某进制下的大数取模,窗口右移一位时,可在 O(1) 时间内由旧哈希推出新哈希,避免重复计算。平均复杂度 O(n+m),最坏(大量碰撞)退化为 O(nm)。

应用

特别适合同时查找多个等长模式(将所有模式哈希放入集合)、文档抄袭检测、数据去重分块(如 rsync 的滑动校验和思想)等场景。

优缺点

实现简单、易扩展到二维匹配;缺点是性能依赖哈希函数质量,存在被构造碰撞攻击的风险,工程中常用随机化模数缓解。