数据结构与算法 / 系统课时

Rabin-Karp 算法

Rabin-Karp 算法

Rabin-Karp 用哈希值快速筛选可能匹配的窗口,再用原字符串比较确认结果。它特别适合在长文本中查找模式串,也能自然扩展到多模式匹配。本课将完成滚动哈希、窗口更新和冲突验证的完整实现。

学习目标

  • 理解字符串哈希与滚动窗口的关系。
  • 掌握常数时间更新窗口哈希值的方法。
  • 能够实现带哈希冲突验证的 Rabin-Karp 搜索。

问题定义

给定长度为 n 的文本 text 和长度为 m 的模式串 pattern,目标是找出所有满足 text[start, start + m) = pattern 的起始下标。

朴素算法会对每个窗口逐字符比较,最坏需要 O(nm) 时间。Rabin-Karp 先比较整数哈希值,仅在哈希相等时检查原字符串,从而减少多数无效窗口的字符比较。

核心原理

字符串哈希把字符序列视为以 BASE 为底的多项式,并对质数 MOD 取模。窗口右移时,不必重新计算全部字符:先移除最左字符的贡献,再乘以 BASE,最后加入新字符。

Rabin-Karp 滚动哈希与冲突验证流程

哈希相等不代表字符串一定相等,因为不同字符串可能得到相同余数。因此,windowHash == patternHash 只能作为候选条件,最终还要调用逐字符比较完成确认。

执行过程

  1. 处理模式串为空或长度大于文本的边界。
  2. 计算 BASE^(m - 1) mod MOD,用于删除窗口最左字符。
  3. 计算模式串和首个文本窗口的哈希值。
  4. 从左到右扫描所有窗口;哈希相等时验证原字符串。
  5. 删除旧窗口首字符的贡献,并加入下一个字符,得到新窗口哈希。

更新时先加上 MOD 再取模,可以避免 Java 中减法结果为负数。窗口长度始终保持为 m,否则最左字符的权重会发生变化。

完整可运行示例

下面的 Java 17 程序查找文本中全部 CDD,并返回从 0 开始的匹配位置。将代码保存为 RabinKarpDemo.java。

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));
    }
}

编译并运行:

bash
javac RabinKarpDemo.java
java RabinKarpDemo

预期输出

text
文本: 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,避免负哈希继续参与计算。
  • 模式串比文本长仍访问首窗口:应在计算哈希前直接返回空结果。

本课练习

  1. 修改示例,使其查找 ABA 在 ABABABA 中的全部位置,验收结果应为 [0, 2, 4]。
  2. 为 search 增加忽略英文字母大小写的选项,要求文本和模式使用同一规范化规则。
  3. 统计哈希相等次数与真实匹配次数,并构造一个小模数实验观察冲突,但最终结果仍必须经过字符串验证。

本课总结

  • Rabin-Karp 用哈希快速排除不可能匹配的窗口。
  • 滚动哈希让相邻窗口的更新成本降为 O(1)。
  • 哈希相等只是候选条件,原字符串验证决定最终正确性。

下一课预告

下一课将学习「Trie 树」,利用公共前缀共享节点,实现字符串集合的插入、完整查询与前缀查询。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

Rabin-Karp 算法

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通