Rabin-Karp算法详解（Java语言实现字符串匹配的高效哈希方法）

为什么使用哈希？

直接逐字符比较每个位置的时间复杂度为 O(nm)，其中 n 是文本长度，m 是模式串长度。而 Rabin-Karp 利用滚动哈希（rolling hash），可以在 O(1) 时间内更新窗口的哈希值，从而将平均时间复杂度优化到 O(n + m)。

Java 实现步骤

我们将按以下步骤实现：

1. 选择一个合适的基数（base）和模数（prime modulus）
2. 计算模式串的哈希值
3. 计算文本中第一个窗口的哈希值
4. 滑动窗口，利用滚动哈希快速更新哈希值
5. 当哈希值匹配时，进行字符级验证

完整 Java 代码示例

public class RabinKarp {    // 基数，通常取一个大于字符集大小的质数    private static final int BASE = 256;    // 大质数，用于防止哈希溢出    private static final long PRIME = 1000000007;    public static void search(String pattern, String text) {        int m = pattern.length();        int n = text.length();        // 如果模式串比文本还长，直接返回        if (m > n) {            return;        }        // 计算 BASE^(m-1) % PRIME，用于滚动哈希        long h = 1;        for (int i = 0; i < m - 1; i++) {            h = (h * BASE) % PRIME;        }        // 计算模式串和文本前 m 个字符的哈希值        long patternHash = 0;        long textHash = 0;        for (int i = 0; i < m; i++) {            patternHash = (patternHash * BASE + pattern.charAt(i)) % PRIME;            textHash = (textHash * BASE + text.charAt(i)) % PRIME;        }        // 滑动窗口遍历文本        for (int i = 0; i <= n - m; i++) {            // 如果哈希值匹配，再逐字符验证            if (patternHash == textHash) {                boolean match = true;                for (int j = 0; j < m; j++) {                    if (text.charAt(i + j) != pattern.charAt(j)) {                        match = false;                        break;                    }                }                if (match) {                    System.out.println("Pattern found at index: " + i);                }            }            // 更新滚动哈希（移除最左字符，添加新字符）            if (i < n - m) {                textHash = (BASE * (textHash - text.charAt(i) * h) + text.charAt(i + m)) % PRIME;                // 防止负数                if (textHash < 0) {                    textHash += PRIME;                }            }        }    }    // 测试示例    public static void main(String[] args) {        String text = "ABABCABABA";        String pattern = "ABABA";        search(pattern, text);    }}  

代码说明

• BASE = 256：因为我们处理的是 ASCII 字符，共 256 个可能值。
• PRIME = 1000000007：一个大质数，用于模运算，减少哈希冲突。
• 滚动哈希公式：new_hash = (BASE * (old_hash - old_char * h) + new_char) % PRIME
• 每次哈希匹配后仍需逐字符验证，因为哈希冲突可能导致误判。

时间复杂度分析

- 平均情况：O(n + m)，得益于高效的滚动哈希。

- 最坏情况：O(nm)，当哈希冲突频繁发生时（如所有子串哈希值都相同）。

适用场景

Rabin-Karp 算法特别适合以下场景：

• 需要同时查找多个模式串（可配合布隆过滤器）
• 文本较长，但模式串较短
• 允许一定概率的误报（可通过二次验证消除）

总结

通过本教程，你已经掌握了如何用 Java语言 实现 Rabin-Karp算法 进行高效的 字符串匹配。该算法的核心在于 哈希算法 的巧妙应用，既提升了性能，又保持了代码的简洁性。希望你能将此方法应用到实际项目中，解决文本搜索问题！

© 2023 字符串匹配算法学习指南 | Rabin-Karp 算法实战