每日算法 — 使用java实现Rabin-Karp：滚动哈希与多模式字符串匹配

一、算法原理

Rabin-Karp 算法的核心思想是将字符串看作一个基于字符的多项式，通过哈希函数将字符串映射为整数。这样，模式串与文本子串的比较就从 O(m) 的字符逐个比较，转化为 O(1) 的哈希值比较。

多项式哈希公式：

H(s) = (s[0] * base^(m-1) + s[1] * base^(m-2) + ... + s[m-1]) mod MOD

滚动更新：当窗口从位置 i 滑动到 i+1 时，新哈希可由旧哈希在 O(1) 时间计算：

H(i+1) = ((H(i) - s[i] * base^(m-1)) * base + s[i+m]) mod MOD

二、单模式匹配实现

import java.util.*;

/**
 * Rabin-Karp 字符串匹配算法实现
 * 支持单模式与多模式匹配，采用双哈希防止碰撞
 */
public class RabinKarp {

    // 两个大质数模数，用于双哈希
    private static final long MOD1 = 1_000_000_007L;
    private static final long MOD2 = 1_000_000_009L;
    // 基数：大于字符集大小即可，常用 91138233、357 等
    private static final long BASE1 = 91138233L;
    private static final long BASE2 = 97266353L;

    /**
     * 单模式 Rabin-Karp 匹配（双哈希版）
     * @param text 文本串
     * @param pattern 模式串
     * @return 所有匹配起始位置列表
     */
    public static List<Integer> search(String text, String pattern) {
        List<Integer> results = new ArrayList<>();
        int n = text.length();
        int m = pattern.length();
        if (m > n || m == 0) return results;

        // 预计算 base^(m-1) mod MOD
        long pow1 = modPow(BASE1, m - 1, MOD1);
        long pow2 = modPow(BASE2, m - 1, MOD2);

        // 计算模式串哈希
        long patHash1 = 0, patHash2 = 0;
        for (int i = 0; i < m; i++) {
            patHash1 = (patHash1 * BASE1 + pattern.charAt(i)) % MOD1;
            patHash2 = (patHash2 * BASE2 + pattern.charAt(i)) % MOD2;
        }

        // 计算文本第一个窗口的哈希
        long txtHash1 = 0, txtHash2 = 0;
        for (int i = 0; i < m; i++) {
            txtHash1 = (txtHash1 * BASE1 + text.charAt(i)) % MOD1;
            txtHash2 = (txtHash2 * BASE2 + text.charAt(i)) % MOD2;
        }

        // 滑动窗口比较
        for (int i = 0; i <= n - m; i++) {
            if (txtHash1 == patHash1 && txtHash2 == patHash2) {
                // 双哈希相等时，进行字符级确认（防止哈希碰撞）
                if (text.substring(i, i + m).equals(pattern)) {
                    results.add(i);
                }
            }

            // 滚动更新哈希（如果不是最后一个窗口）
            if (i < n - m) {
                // 移除最左边字符的贡献
                txtHash1 = (txtHash1 - text.charAt(i) * pow1 % MOD1 + MOD1) % MOD1;
                txtHash2 = (txtHash2 - text.charAt(i) * pow2 % MOD2 + MOD2) % MOD2;

                // 左移并加入新字符
                txtHash1 = (txtHash1 * BASE1 + text.charAt(i + m)) % MOD1;
                txtHash2 = (txtHash2 * BASE2 + text.charAt(i + m)) % MOD2;
            }
        }

        return results;
    }

    /**
     * 快速幂：计算 (base^exp) mod mod
     */
    private static long modPow(long base, long exp, long mod) {
        long result = 1 % mod;
        long b = base % mod;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = (result * b) % mod;
            }
            b = (b * b) % mod;
            exp >>= 1;
        }
        return result;
    }

三、多模式匹配扩展

    /**
     * 多模式 Rabin-Karp 匹配
     * 将所有模式串的哈希存入哈希表，一次遍历文本同时匹配所有模式
     * @param text 文本串
     * @param patterns 模式串数组
     * @return 每个模式串的匹配位置列表
     */
    public static Map<String, List<Integer>> multiPatternSearch(String text, String[] patterns) {
        Map<String, List<Integer>> results = new HashMap<>();
        for (String p : patterns) {
            results.put(p, new ArrayList<>());
        }

        int n = text.length();
        if (patterns.length == 0 || n == 0) return results;

        // 按长度分组模式串
        Map<Integer, Set<Long>> patternHashesByLen = new HashMap<>();
        Map<Long, List<String>> hashToPatterns = new HashMap<>();

        for (String p : patterns) {
            int m = p.length();
            if (m > n) continue;

            long h1 = 0;
            for (int i = 0; i < m; i++) {
                h1 = (h1 * BASE1 + p.charAt(i)) % MOD1;
            }

            patternHashesByLen.computeIfAbsent(m, k -> new HashSet<>()).add(h1);
            hashToPatterns.computeIfAbsent(h1 * n + m, k -> new ArrayList<>()).add(p);
        }

        // 对每个不同长度分别进行滚动哈希扫描
        for (Map.Entry<Integer, Set<Long>> entry : patternHashesByLen.entrySet()) {
            int m = entry.getKey();
            Set<Long> targetHashes = entry.getValue();

            long pow1 = modPow(BASE1, m - 1, MOD1);
            long txtHash = 0;

            // 初始化第一个窗口
            for (int i = 0; i < m; i++) {
                txtHash = (txtHash * BASE1 + text.charAt(i)) % MOD1;
            }

            for (int i = 0; i <= n - m; i++) {
                if (targetHashes.contains(txtHash)) {
                    // 找到候选，验证所有该长度的模式串
                    String sub = text.substring(i, i + m);
                    List<String> candidates = hashToPatterns.get(txtHash * n + m);
                    if (candidates != null) {
                        for (String p : candidates) {
                            if (sub.equals(p)) {
                                results.get(p).add(i);
                            }
                        }
                    }
                }

                if (i < n - m) {
                    txtHash = (txtHash - text.charAt(i) * pow1 % MOD1 + MOD1) % MOD1;
                    txtHash = (txtHash * BASE1 + text.charAt(i + m)) % MOD1;
                }
            }
        }

        return results;
    }

四、二维 Rabin-Karp（图像子图匹配）

    /**
     * 二维 Rabin-Karp：在字符矩阵中搜索子矩阵
     * 先对每行做滚动哈希，再对列做滚动哈希
     */
    public static List<int[]> search2D(char[][] matrix, char[][] pattern) {
        List<int[]> results = new ArrayList<>();
        int R = matrix.length, C = matrix[0].length;
        int r = pattern.length, c = pattern[0].length;
        if (r > R || c > C) return results;

        // 对每行计算水平方向的滚动哈希
        long[][] rowHash = new long[R][C - c + 1];
        long powC = modPow(BASE1, c - 1, MOD1);

        for (int i = 0; i < R; i++) {
            long h = 0;
            for (int j = 0; j < c; j++) {
                h = (h * BASE1 + matrix[i][j]) % MOD1;
            }
            rowHash[i][0] = h;
            for (int j = 1; j <= C - c; j++) {
                h = (h - matrix[i][j - 1] * powC % MOD1 + MOD1) % MOD1;
                h = (h * BASE1 + matrix[i][j + c - 1]) % MOD1;
                rowHash[i][j] = h;
            }
        }

        // 对列做垂直方向的滚动哈希
        long powR = modPow(BASE2, r - 1, MOD2);
        long patHash = 0;
        for (int i = 0; i < r; i++) {
            long rowH = 0;
            for (int j = 0; j < c; j++) {
                rowH = (rowH * BASE1 + pattern[i][j]) % MOD1;
            }
            patHash = (patHash * BASE2 + rowH) % MOD2;
        }

        for (int j = 0; j <= C - c; j++) {
            long colHash = 0;
            for (int i = 0; i < r; i++) {
                colHash = (colHash * BASE2 + rowHash[i][j]) % MOD2;
            }
            if (colHash == patHash) {
                // 验证
                boolean match = true;
                for (int di = 0; di < r && match; di++) {
                    for (int dj = 0; dj < c; dj++) {
                        if (matrix[di][j + dj] != pattern[di][dj]) {
                            match = false;
                            break;
                        }
                    }
                }
                if (match) results.add(new int[]{0, j});
            }

            for (int i = 1; i <= R - r; i++) {
                colHash = (colHash - rowHash[i - 1][j] * powR % MOD2 + MOD2) % MOD2;
                colHash = (colHash * BASE2 + rowHash[i + r - 1][j]) % MOD2;
                if (colHash == patHash) {
                    boolean match = true;
                    for (int di = 0; di < r && match; di++) {
                        for (int dj = 0; dj < c; dj++) {
                            if (matrix[i + di][j + dj] != pattern[di][dj]) {
                                match = false;
                                break;
                            }
                        }
                    }
                    if (match) results.add(new int[]{i, j});
                }
            }
        }

        return results;
    }

五、完整测试与演示

    /**
     * 主程序：测试单模式、多模式与二维匹配
     */
    public static void main(String[] args) {
        System.out.println("=== 单模式匹配测试 ===");
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        List<Integer> single = search(text, pattern);
        System.out.println("文本: " + text);
        System.out.println("模式: " + pattern);
        System.out.println("匹配位置: " + single);

        System.out.println("
=== 多模式匹配测试 ===");
        String text2 = "The quick brown fox jumps over the lazy dog. The fox was quick.";
        String[] patterns = {"fox", "quick", "dog", "cat"};
        Map<String, List<Integer>> multi = multiPatternSearch(text2, patterns);
        for (Map.Entry<String, List<Integer>> e : multi.entrySet()) {
            System.out.println(e.getKey() + " -> " + e.getValue());
        }

        System.out.println("
=== 二维匹配测试 ===");
        char[][] matrix = {
            "abcdef".toCharArray(),
            "ghijkl".toCharArray(),
            "mnopqr".toCharArray(),
            "stuvwx".toCharArray()
        };
        char[][] pat2D = {
            "jkl".toCharArray(),
            "pqr".toCharArray()
        };
        List<int[]> results2D = search2D(matrix, pat2D);
        for (int[] pos : results2D) {
            System.out.println("2D 匹配位置: (" + pos[0] + ", " + pos[1] + ")");
        }
    }
}

六、复杂度分析

场景	平均时间复杂度	最坏时间复杂度	空间复杂度
单模式	O(n + m)	O(n × m)（哈希碰撞时）	O(1)
多模式（k个模式总长M）	O(n + M)	O(n × M)	O(M)
二维匹配（R×C矩阵，r×c模式）	O(R × C)	O(R × C × r × c)	O(R × C)

双哈希策略：使用两个独立的大质数模数后，随机碰撞概率降至约 1/(MOD1 × MOD2) ≈ 10⁻¹⁸，实际应用中可以认为不会发生。

七、应用场景

** plagiarism 检测**：将文档切片后做滚动哈希，快速查找重复片段
DNA 序列分析：在基因组中高效搜索多个特征序列
图像匹配：二维 Rabin-Karp 用于快速模板匹配
滚动去重：数据流中的滑动窗口去重（配合布隆过滤器）

Rabin-Karp 用哈希将字符串比较转化为整数比较，是理解滚动技术与概率算法的经典范例。

Tagged with: Java Rabin-Karp 双哈希多项式哈希字符串匹配模式搜索滚动哈希