数据结构与算法 / 系统课时
Rabin-Karp 算法
Rabin-Karp 算法
Rabin-Karp 用哈希值快速筛选可能匹配的窗口,再用原字符串比较确认结果。它特别适合在长文本中查找模式串,也能自然扩展到多模式匹配。本课将完成滚动哈希、窗口更新和冲突验证的完整实现。
学习目标
- 理解字符串哈希与滚动窗口的关系。
- 掌握常数时间更新窗口哈希值的方法。
- 能够实现带哈希冲突验证的 Rabin-Karp 搜索。
问题定义
给定长度为 n 的文本 text 和长度为 m 的模式串 pattern,目标是找出所有满足 text[start, start + m) = pattern 的起始下标。
朴素算法会对每个窗口逐字符比较,最坏需要 O(nm) 时间。Rabin-Karp 先比较整数哈希值,仅在哈希相等时检查原字符串,从而减少多数无效窗口的字符比较。
核心原理
字符串哈希把字符序列视为以 BASE 为底的多项式,并对质数 MOD 取模。窗口右移时,不必重新计算全部字符:先移除最左字符的贡献,再乘以 BASE,最后加入新字符。

哈希相等不代表字符串一定相等,因为不同字符串可能得到相同余数。因此,windowHash == patternHash 只能作为候选条件,最终还要调用逐字符比较完成确认。
执行过程
- 处理模式串为空或长度大于文本的边界。
- 计算
BASE^(m - 1) mod MOD,用于删除窗口最左字符。 - 计算模式串和首个文本窗口的哈希值。
- 从左到右扫描所有窗口;哈希相等时验证原字符串。
- 删除旧窗口首字符的贡献,并加入下一个字符,得到新窗口哈希。
更新时先加上 MOD 再取模,可以避免 Java 中减法结果为负数。窗口长度始终保持为 m,否则最左字符的权重会发生变化。
完整可运行示例
下面的 Java 17 程序查找文本中全部 CDD,并返回从 0 开始的匹配位置。将代码保存为 RabinKarpDemo.java。
import java.util.ArrayList;
import java.util.List;
public class RabinKarpDemo {
private static final long BASE = 256;
private static final long MOD = 1_000_000_007L;
public static List<Integer> search(String text, String pattern) {
List<Integer> matches = new ArrayList<>();
int n = text.length();
int m = pattern.length();
if (m == 0 || m > n) {
return matches;
}
long highestPower = 1;
for (int i = 1; i < m; i++) {
highestPower = (highestPower * BASE) % MOD;
}
long patternHash = 0;
long windowHash = 0;
for (int i = 0; i < m; i++) {
patternHash = (patternHash * BASE + pattern.charAt(i)) % MOD;
windowHash = (windowHash * BASE + text.charAt(i)) % MOD;
}
for (int start = 0; start <= n - m; start++) {
// 哈希相等后仍比较原字符串,避免哈希冲突造成误报。
if (windowHash == patternHash && equalsAt(text, pattern, start)) {
matches.add(start);
}
if (start < n - m) {
long outgoing = text.charAt(start);
long incoming = text.charAt(start + m);
// 删除窗口最左字符,再追加新的最右字符。
windowHash = (windowHash - outgoing * highestPower % MOD + MOD) % MOD;
windowHash = (windowHash * BASE + incoming) % MOD;
}
}
return matches;
}
private static boolean equalsAt(String text, String pattern, int start) {
for (int i = 0; i < pattern.length(); i++) {
if (text.charAt(start + i) != pattern.charAt(i)) {
return false;
}
}
return true;
}
public static void main(String[] args) {
String text = "ABCCDDAEFGCDD";
String pattern = "CDD";
System.out.println("文本: " + text);
System.out.println("模式: " + pattern);
System.out.println("匹配位置: " + search(text, pattern));
}
}编译并运行:
javac RabinKarpDemo.java
java RabinKarpDemo预期输出
文本: ABCCDDAEFGCDD
模式: CDD
匹配位置: [3, 10]复杂度与边界
预处理模式串和首个窗口需要 O(m) 时间,每次窗口哈希更新需要 O(1) 时间。在哈希分布良好时,总体通常为 O(n + m);如果大量窗口哈希相等并触发完整验证,最坏时间仍可能达到 O(nm)。
除结果列表外,算法只维护若干哈希变量,额外空间为 O(1)。示例按 Java 的 char 处理 UTF-16 代码单元;处理完整 Unicode 码点时,应改用 codePoints() 生成整数序列。
常见错误
- 只比较哈希值:哈希冲突会产生误报。修复方法是在哈希相等后调用
equalsAt。 - 删除字符时使用错误权重:最左字符必须乘以
BASE^(m - 1),否则滚动结果与重新计算不一致。 - 忘记修正负数:表达式应使用
(value + MOD) % MOD,避免负哈希继续参与计算。 - 模式串比文本长仍访问首窗口:应在计算哈希前直接返回空结果。
本课练习
- 修改示例,使其查找
ABA在ABABABA中的全部位置,验收结果应为[0, 2, 4]。 - 为
search增加忽略英文字母大小写的选项,要求文本和模式使用同一规范化规则。 - 统计哈希相等次数与真实匹配次数,并构造一个小模数实验观察冲突,但最终结果仍必须经过字符串验证。
本课总结
- Rabin-Karp 用哈希快速排除不可能匹配的窗口。
- 滚动哈希让相邻窗口的更新成本降为
O(1)。 - 哈希相等只是候选条件,原字符串验证决定最终正确性。
下一课预告
下一课将学习「Trie 树」,利用公共前缀共享节点,实现字符串集合的插入、完整查询与前缀查询。