简介

在一个超长的字符串中，只要做了 O(n) 的预处理，之后查询任一子串的哈希值，其时间复杂度都是 O(1) 。适用于需要频繁比较子串的场景，如重复子串查找、最长重复子串等。

算法原理

1. 前缀哈希数组：h[i] 表示字符串前i个字符的哈希值。计算方式为：

   h[i] = h[i-1] * P + s.charAt(i-1)
   

   其中P为基数（通常取大质数，如131、13331等），通过累积计算每个字符的贡献。

2. 幂次数组：p[i] 存储P的i次幂，用于快速计算子串哈希：

   p[i] = p[i-1] * P
   

3. 子串哈希计算：子串 s[a..b]（0-based，闭区间）的哈希值为：

   hash = h[b+1] - h[a] * p[b - a + 1]
   

   该公式通过前缀哈希的差值乘以对应幂次，消除高位影响。

可以看到整个过程原理类似于前缀和，只要构造出前缀和数组，求区间和时间复杂度就是 O(1)。

代码模板

例题：https://leetcode.cn/problems/repeated-dna-sequences/description/

}

class Solution {
    private static final int P = 131313; // 或更大的质数
    private int[] h, p;

    public List<String> findRepeatedDnaSequences(String s) {
        int n = s.length();
        List<String> ans = new ArrayList<>();
        h = new int[n + 1];
        p = new int[n + 1];
        p[0] = 1;

        // 预处理前缀哈希和幂次数组
        for (int i = 1; i <= n; i++) {
            h[i] = h[i - 1] * P + s.charAt(i - 1);
            p[i] = p[i - 1] * P;
        }

        Map<Integer, Integer> count = new HashMap<>();
        for (int i = 1; i + 9 <= n; i++) { // 遍历所有长度为10的子串
            int j = i + 9; // 子串结束位置的前缀索引
            int hash = h[j] - h[i - 1] * p[10]; // 计算哈希
            int cnt = count.getOrDefault(hash, 0);
            if (cnt == 1) ans.add(s.substring(i - 1, i + 9)); // 第二次出现时加入结果
            count.put(hash, cnt + 1);
        }
        return ans;
    }
}

如何解决哈希冲突？

由于哈希冲突的存在，可能会导致：两个不同的字符串，经过计算得到的哈希值相同。

解决方案：一个比较方便的方法是取两个基数 P1 P2。这样一个字符串可以得到两个不同的哈希值。

单基数的哈希冲突的几率如果是万分之一，那么双基数的哈希冲突的几率就是亿分之一了。