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

字符串匹配是计算机科学中最基础也最重要的问题之一。从文本编辑器的查找替换到搜索引擎的关键词检索，从DNA序列比对到网络入侵检测，高效的字符串匹配算法无处不在。本文将深入讲解字符串哈希的核心原理，用Java实现Rabin-Karp滚动哈希算法，并展示其在多模式匹配中的应用。

一、字符串哈希原理

1.1 多项式滚动哈希

将字符串视为一个以字符ASCII码为系数的多项式，在模一个大质数 P 的意义下求值：

H(s) = (s[0]·B^(n-1) + s[1]·B^(n-2) + ... + s[n-1]·B^0) mod P

其中 B 为基数（通常取131或13131），P 为模数（通常取大质数如 10^9+7）。

1.2 哈希冲突与双哈希

哈希冲突是指不同字符串产生相同哈希值。虽然概率极低，但在安全性要求高的场景下，可采用双哈希策略：使用两组不同的 (B, P) 参数分别计算哈希值，将 (h1, h2) 作为指纹，冲突概率降至 1/P²。

1.3 滚动哈希的高效更新

Rabin-Karp算法的精髓在于：已知子串 s[i..i+m-1] 的哈希值，可以在 O(1) 时间内计算出 s[i+1..i+m] 的哈希值。

假设当前哈希值为：

H = s[i]·B^(m-1) + s[i+1]·B^(m-2) + ... + s[i+m-1]·B^0

向右滚动一位后：

H' = (H - s[i]·B^(m-1)) · B + s[i+m]

所有运算在模 P 意义下进行。

二、核心算法设计

2.1 Rabin-Karp单模式匹配

1. 计算模式串 pattern 的哈希值 hashP
2. 预处理计算 B^(m-1) mod P
3. 计算文本串 text 前 m 个字符的哈希值
4. 从 i=0 开始向右滚动，每次比较 hashText 与 hashP
5. 若哈希相等，进行逐字符验证（防止冲突）
6. 使用滚动公式更新哈希值，继续下一轮

时间复杂度：O(n+m) 平均，O(nm) 最坏（冲突频繁时）

2.2 多模式匹配扩展

当有 k 个模式串时，可将所有模式串的哈希值存入哈希集合。遍历文本时，对每个位置检查当前子串哈希是否在集合中。

时间复杂度：O(n + 所有模式串长度之和)

2.3 最长公共前缀（LCP）查询

利用前缀哈希数组，可以在 O(1) 时间内比较任意两个子串是否相等，进而用二分查找在 O(log n) 时间内求LCP。

三、Java完整实现

import java.util.*;

/**
 * 字符串哈希算法实现
 * 包含Rabin-Karp滚动哈希、多模式匹配与LCP查询
 */
public class StringHash {

    // 双哈希参数，大幅降低冲突概率
    private static final long B1 = 131;
    private static final long P1 = 1_000_000_007L;
    private static final long B2 = 13131;
    private static final long P2 = 1_000_000_009L;

    private long[] pow1, pow2;      // 幂次数组
    private long[] prefix1, prefix2; // 前缀哈希数组
    private String text;

    /**
     * 构建字符串的前缀哈希数组
     * @param s 目标字符串
     */
    public StringHash(String s) {
        this.text = s;
        int n = s.length();
        pow1 = new long[n + 1];
        pow2 = new long[n + 1];
        prefix1 = new long[n + 1];
        prefix2 = new long[n + 1];

        pow1[0] = pow2[0] = 1;
        for (int i = 1; i <= n; i++) {
            pow1[i] = (pow1[i - 1] * B1) % P1;
            pow2[i] = (pow2[i - 1] * B2) % P2;
        }

        for (int i = 0; i < n; i++) {
            int c = s.charAt(i);
            prefix1[i + 1] = (prefix1[i] * B1 + c) % P1;
            prefix2[i + 1] = (prefix2[i] * B2 + c) % P2;
        }
    }

    /**
     * 获取子串 [l, r] 的双哈希值（0-based，闭区间）
     */
    public long[] getHash(int l, int r) {
        long h1 = (prefix1[r + 1] - (prefix1[l] * pow1[r - l + 1]) % P1 + P1) % P1;
        long h2 = (prefix2[r + 1] - (prefix2[l] * pow2[r - l + 1]) % P2 + P2) % P2;
        return new long[]{h1, h2};
    }

    /**
     * 比较两个子串是否相等
     */
    public boolean equals(int l1, int r1, int l2, int r2) {
        if (r1 - l1 != r2 - l2) return false;
        long[] h1 = getHash(l1, r1);
        long[] h2 = getHash(l2, r2);
        return h1[0] == h2[0] && h1[1] == h2[1];
    }

    /**
     * Rabin-Karp单模式匹配
     * @return 所有匹配起始位置
     */
    public List<Integer> rabinKarp(String pattern) {
        List<Integer> matches = new ArrayList<>();
        int m = pattern.length();
        int n = text.length();
        if (m > n) return matches;

        // 计算模式串的哈希值
        long[] patternHash = computeHash(pattern);

        // 滚动比较
        for (int i = 0; i <= n - m; i++) {
            long[] currHash = getHash(i, i + m - 1);
            if (currHash[0] == patternHash[0] && currHash[1] == patternHash[1]) {
                // 哈希相等时进行逐字符验证
                if (text.substring(i, i + m).equals(pattern)) {
                    matches.add(i);
                }
            }
        }
        return matches;
    }

    /**
     * 计算整个字符串的双哈希值
     */
    private long[] computeHash(String s) {
        long h1 = 0, h2 = 0;
        for (int i = 0; i < s.length(); i++) {
            int c = s.charAt(i);
            h1 = (h1 * B1 + c) % P1;
            h2 = (h2 * B2 + c) % P2;
        }
        return new long[]{h1, h2};
    }

    /**
     * 多模式匹配：在文本中查找多个模式串的出现位置
     */
    public Map<String, List<Integer>> multiPatternMatch(String[] patterns) {
        Map<String, List<Integer>> result = new LinkedHashMap<>();

        // 构建模式串哈希集合
        Set<Long> patternHashSet = new HashSet<>();
        Map<Long, List<String>> hashToPatterns = new HashMap<>();

        for (String p : patterns) {
            long[] h = computeHash(p);
            // 使用双哈希组合：h1 * P2 + h2
            long combined = h[0] * P2 + h[1];
            patternHashSet.add(combined);
            hashToPatterns.computeIfAbsent(combined, k -> new ArrayList<>()).add(p);
        }

        // 找出最短和最长模式长度
        int minLen = Integer.MAX_VALUE, maxLen = 0;
        for (String p : patterns) {
            minLen = Math.min(minLen, p.length());
            maxLen = Math.max(maxLen, p.length());
        }

        // 对每个可能的长度进行滚动匹配
        for (int len = minLen; len <= maxLen; len++) {
            for (int i = 0; i <= text.length() - len; i++) {
                long[] h = getHash(i, i + len - 1);
                long combined = h[0] * P2 + h[1];

                if (patternHashSet.contains(combined)) {
                    for (String p : hashToPatterns.get(combined)) {
                        if (p.length() == len && text.substring(i, i + len).equals(p)) {
                            result.computeIfAbsent(p, k -> new ArrayList<>()).add(i);
                        }
                    }
                }
            }
        }

        return result;
    }

    /**
     * 最长公共前缀（LCP）查询
     * 返回 text[l1..] 与 text[l2..] 的最长公共前缀长度
     */
    public int lcp(int l1, int l2) {
        int n = text.length();
        int maxLen = Math.min(n - l1, n - l2);

        // 二分查找LCP长度
        int left = 0, right = maxLen;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (equals(l1, l1 + mid - 1, l2, l2 + mid - 1)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    /**
     * 最长重复子串长度
     */
    public int longestRepeatedSubstring() {
        int n = text.length();
        int result = 0;

        // 枚举长度，使用哈希集合检测重复
        for (int len = 1; len <= n; len++) {
            Set<Long> seen = new HashSet<>();
            boolean found = false;
            for (int i = 0; i <= n - len; i++) {
                long[] h = getHash(i, i + len - 1);
                long combined = h[0] * P2 + h[1];
                if (seen.contains(combined)) {
                    // 验证避免冲突
                    String sub = text.substring(i, i + len);
                    for (int j = 0; j < i; j++) {
                        if (text.substring(j, j + len).equals(sub)) {
                            found = true;
                            result = len;
                            break;
                        }
                    }
                    if (found) break;
                }
                seen.add(combined);
            }
            if (!found) break; // 当前长度无重复，更长长度也不会有
        }
        return result;
    }

    public static void main(String[] args) {
        String text = "abracadabraabracadabra";
        StringHash sh = new StringHash(text);

        System.out.println("=== 字符串哈希算法演示 ===\n");
        System.out.println("文本: " + text + "\n");

        // 1. Rabin-Karp单模式匹配
        String pattern = "abra";
        List<Integer> matches = sh.rabinKarp(pattern);
        System.out.println("模式 '" + pattern + "' 的匹配位置: " + matches);

        // 2. 多模式匹配
        String[] patterns = {"abra", "cada", "braa", "xyz"};
        Map<String, List<Integer>> multiResult = sh.multiPatternMatch(patterns);
        System.out.println("\n多模式匹配结果:");
        for (Map.Entry<String, List<Integer>> entry : multiResult.entrySet()) {
            System.out.println("  '" + entry.getKey() + "': " + entry.getValue());
        }

        // 3. LCP查询
        int lcpResult = sh.lcp(0, 11);
        System.out.println("\nLCP(0, 11) = " + lcpResult);
        System.out.println("  text[0..] = " + text.substring(0, Math.min(15, text.length())));
        System.out.println("  text[11..] = " + text.substring(11, Math.min(26, text.length())));

        // 4. 最长重复子串
        int longest = sh.longestRepeatedSubstring();
        System.out.println("\n最长重复子串长度: " + longest);

        // 5. 子串相等测试
        boolean eq = sh.equals(0, 3, 11, 14);
        System.out.println("text[0..3] == text[11..14]: " + eq);
    }
}

四、算法复杂度分析

五、应用场景与扩展

1. DNA序列比对：处理由{A,C,G,T}组成的超长字符串，基数B取4
2. ** plagiarism检测**：将文档分词后构建哈希指纹，快速比对相似度
3. 滚动哈希的模运算技巧：利用 (a - b) % P = (a % P - b % P + P) % P 避免负数
4. 自然溢出：使用 long 类型自然溢出替代显式取模，速度更快但冲突率略高

六、总结

字符串哈希将复杂的字符串比较转化为高效的整数比较，是处理大规模文本问题的利器：

• 多项式哈希 将字符串映射为指纹整数
• 滚动更新 在O(1)时间内滑动窗口哈希值
• 双哈希策略 将冲突概率降至可忽略级别
• 前缀哈希数组 支持任意子串的O(1)哈希查询

Rabin-Karp算法虽在最坏情况下不如KMP稳定，但在实际应用中配合双哈希几乎不可能发生冲突，且实现简洁、易于扩展，是工程实践中的首选方案之一。