字符串 · 哈希（多项式哈希 + 滚动哈希）

从 LC 28 出发，看字符串哈希怎么把"两个等长子串是否相同"压到 O(1) 比较。

Hard预计阅读 50 分钟更新于 2026-05-19

1. 核心原理

字符串哈希（string hashing，又称 Rabin-Karp 哈希）把"长度为 m 的子串是否相等"压成"两个整数是否相等"。和 KMP 一样能在 O(n + m) 时间里完成模式匹配，但额外能 O(1) 比较任意两个等长子串——这件事 KMP 做不到。代价是有极小概率的哈希碰撞（不同子串映射到同一个整数），需要兜底处理。

多项式哈希定义

把字符串 s = s[0] s[1] ... s[k-1] 映射成整数：

hash(s) = (s[0] * base^(k-1) + s[1] * base^(k-2) + ... + s[k-1] * base^0) mod p

base 是一个比字符集大的"进制"，p 是一个大质数取模数。两个常见组合：

base = 131 或 233（ASCII / 小写字母够用），p = 10⁹ + 7
双哈希：跑两套 (base, p)，比较两个整数对都相等才认为字符串相等

碰撞概率怎么估：单次随机比较的碰撞率约 1 / p。扫 n 个窗口共有 C(n, 2) ≈ n² / 2 对比较，由生日悖论期望碰撞次数 ≈ n² / (2p)：

p = 10⁹ + 7、n = 10⁵ → 期望碰撞 ≈ 5（够多了，单哈希 LC 大数据可能挂）
p = 2⁶¹ − 1 ≈ 2.3 × 10¹⁸、n = 10⁵ → 期望碰撞 ≈ 2 × 10⁻⁹（实际零风险）
双哈希 (p₁, p₂) → 碰撞率 1 / (p₁ p₂)，n=10⁵ 时 ≈ 10⁻⁹ 以下，竞赛标配

历史上 LC 评测出现过针对单哈希 10⁹+7 的 hack 用例，所以大数据竞赛 / 工业代码常上双哈希或 Mersenne 大模数。

前缀哈希 + 区间查询

对长度 n 的字符串 s 预处理前缀哈希 H[i] = hash(s[0..i-1])。即 H[0] = 0，H[i+1] = H[i] * base + s[i]。

要查询子串 s[l..r-1]（长度 r - l）的哈希值，套公式：

hash(s[l..r-1]) = H[r] - H[l] * base^(r-l)    (mod p)

理解：H[r] 已经把前 r 个字符按多项式累乘起来；前 l 个字符的部分在 H[l] 里，要"对齐"到 r 长度，得乘上 base^(r-l) 再减掉。

预处理 H 和幂表各 O(n)，之后任意子串哈希 O(1) 查询。这是字符串哈希最重要的副产品——它不止能加速单次匹配，还能加速任何"等长子串比较"。

滚动哈希（定长窗口版）

如果只关心"长度固定为 m 的子串"，可以不存前缀哈希，直接维护一个"当前窗口的哈希值"：

window[0]   = s[0]   * base^(m-1) + s[1] * base^(m-2) + ... + s[m-1]
window[i+1] = (window[i] - s[i] * base^(m-1)) * base + s[i+m]

每次 O(1) 更新。本章 §3 母题用前缀版（适合多模式 / 不等长比较），§4.1 用滚动窗口版（适合固定长度扫一遍）。

取模与负数

Python 的 % 对负数返回非负余数，可以直接 (a - b) % p。Java / C++ / Go 的 % 对负数返回负余数，要写 ((a - b) % p + p) % p 才安全。多查询的题里这一行经常被漏掉，导致单测能过、大数据 WA。

怎么选 base 和 p

选项	优点	风险
单哈希 `base = 131, p = 10⁹ + 7`	代码短、常数小	LC 上可能被特意构造的数据 hack
双哈希 `(131, 10⁹+7) + (137, 10⁹+9)`	碰撞概率约 `10⁻¹⁸`	代码量翻倍、常数 2 倍
用 Python 内置 `hash()`	一行搞定	启动后会随机化、不可复现

工程上、北美面试场景下，单哈希足够过 LC 题；竞赛 / 被 hack 数据用双哈希。下面模板给单哈希版，§5 提双哈希的写法。

2. 通用模板

下面给一个通用的字符串哈希类，支持：

构造 O(n)：传入字符串 s，预处理前缀哈希和幂表。
查询 O(1)：get(l, r) 返回 s[l..r-1] 的哈希值（左闭右开）。

§3 母题精讲和 §4 例题都基于这个类调。

class StringHash:
    def __init__(self, s: str, base: int = 131, mod: int = 10 ** 9 + 7):
        n = len(s)
        self.mod = mod
        self.h = [0] * (n + 1)                    # 前缀哈希
        self.p = [1] * (n + 1)                    # base 的幂
        for i, ch in enumerate(s):
            self.h[i + 1] = (self.h[i] * base + ord(ch)) % mod
            self.p[i + 1] = self.p[i] * base % mod

    def get(self, l: int, r: int) -> int:
        # 返回 s[l..r-1] 的哈希值，左闭右开
        return (self.h[r] - self.h[l] * self.p[r - l]) % self.mod


class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n, m = len(haystack), len(needle)
        if m == 0:
            return 0
        if m > n:
            return -1
        base, mod = 131, 10 ** 9 + 7
        # 计算 needle 的哈希
        nh = 0
        for ch in needle:
            nh = (nh * base + ord(ch)) % mod
        # 滚动哈希扫 haystack
        H = StringHash(haystack, base, mod)
        for i in range(n - m + 1):
            if H.get(i, i + m) == nh:
                return i
        return -1

class StringHash {
    long[] h, p;
    long mod;
    public StringHash(String s, long base, long mod) {
        int n = s.length();
        this.mod = mod;
        h = new long[n + 1];
        p = new long[n + 1];
        p[0] = 1;
        for (int i = 0; i < n; i++) {
            h[i + 1] = (h[i] * base + s.charAt(i)) % mod;
            p[i + 1] = p[i] * base % mod;
        }
    }
    public long get(int l, int r) {
        long v = (h[r] - h[l] * p[r - l]) % mod;
        return (v + mod) % mod;               // 负数修正
    }
}

class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        if (m == 0) return 0;
        if (m > n) return -1;
        long base = 131, mod = 1_000_000_007L;
        long nh = 0;
        for (int i = 0; i < m; i++) {
            nh = (nh * base + needle.charAt(i)) % mod;
        }
        StringHash H = new StringHash(haystack, base, mod);
        for (int i = 0; i + m <= n; i++) {
            if (H.get(i, i + m) == nh) return i;
        }
        return -1;
    }
}

class StringHash {
public:
    vector<long long> h, p;                       // 用 long long 防溢出
    long long mod;
    StringHash(const string& s, long long base, long long mod_) : mod(mod_) {
        int n = s.size();
        h.assign(n + 1, 0);                       // 前缀哈希
        p.assign(n + 1, 1);                       // base 的幂
        for (int i = 0; i < n; i++) {
            h[i + 1] = (h[i] * base + s[i]) % mod;
            p[i + 1] = p[i] * base % mod;
        }
    }
    long long get(int l, int r) {
        // 返回 s[l..r-1] 的哈希值，左闭右开
        long long v = (h[r] - h[l] * p[r - l]) % mod;
        return (v + mod) % mod;                   // 负数修正
    }
};

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        if (m == 0) return 0;
        if (m > n) return -1;
        long long base = 131, mod = 1000000007LL;
        long long nh = 0;
        for (int i = 0; i < m; i++) {
            nh = (nh * base + needle[i]) % mod;
        }
        StringHash H(haystack, base, mod);
        for (int i = 0; i + m <= n; i++) {
            if (H.get(i, i + m) == nh) return i;
        }
        return -1;
    }
};

构造 O(n)、单次查询 O(1)、扫一遍找匹配 O(n)。总复杂度 O(n + m)，跟 KMP 同阶，常数略大。

几点要说明：

get(l, r) 是左闭右开：传 (0, m) 取前 m 字符的哈希。统一区间约定避免边界错位。
p[i + 1] = p[i] * base % mod：幂表与 h 同步预处理，避免每次查询重新算 base^k。
Java / C++ 的负数兜底：get 末尾 (v + mod) % mod 保证返回非负。Python 的 % 对负数已自动归正，不需要这步——但模板里写了也不影响正确性。
base 与 mod：模板用 base = 131, mod = 10⁹ + 7，覆盖 LC 普通题。竞赛 / 大数据题改成 mod = (1 << 61) - 1 或上双哈希，详见 §5。

3. 母题精讲

LeetCode 28. Find the Index of the First Occurrence in a String

链接：LeetCode 28

题目（中文翻译）：给两个字符串 haystack（长 n）和 needle（长 m），返回 needle 在 haystack 中第一次出现的下标；不存在返回 -1。

数据范围：

1 ≤ n, m ≤ 10⁴
两个字符串只含小写英文字母

示例：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释：第一个匹配出现在下标 0，第二个匹配出现在下标 6，但题目要求返回第一个。

朴素解：逐位比较

最直观的写法是双层循环：外层枚举 haystack 里的起点 i，内层比较 haystack[i:i+m] 与 needle：

class Solution:
    def strStr_naive(self, haystack: str, needle: str) -> int:
        n, m = len(haystack), len(needle)
        for i in range(n - m + 1):
            if haystack[i:i + m] == needle:        # 切片比较 O(m)
                return i
        return -1

复杂度 O(n × m)。在 haystack = "aaaa...aab"、needle = "aaaab" 这类对抗输入下退化最严重——每个起点都要比到末位才发现失配。

上一章 KMP 用 next 数组把重复比较省掉，做到 O(n + m)。本章换个完全不同的思路：把每个长度为 m 的子串压成整数，比较两个子串相等就变成比较两个整数相等。

哈希解

直接套 §2 模板：预处理 haystack 的前缀哈希，单独算 needle 的整体哈希值，然后扫起点 i 用 O(1) 比较。代码已经在 §2 给出。时间 O(n + m)，空间 O(n) 存前缀哈希。

哈希 vs KMP 的对比

维度	KMP	字符串哈希
时间	`O(n + m)` 最坏保证	`O(n + m)` 平均，碰撞最坏 `O(nm)`
空间	`O(m)` next 数组	`O(n)` 前缀哈希
代码量	next 数组约 20 行	8 行套模板
多次查询同 haystack	next 每次重算	前缀哈希一次预处理后任意子串 `O(1)`
抗 hack	100% 正确	极小概率碰撞
扩展性	只能单模式	任何"等长子串相等"问题都能用

碰撞验证（工程版）：哈希命中后再用 haystack[i:i+m] == needle 做一次字符比较兜底。命中率本来就低，常数代价可忽略：

if H.get(i, i + m) == nh and haystack[i:i + m] == needle:
    return i

碰到"多次询问 / 不同长度子串比较 / 后续题"时，哈希在可扩展性上更有空间——例如 §4.2 的"最长重复子串"，KMP 用不上，哈希套二分一路杀到底。

Follow-up：上面是"在长串里找一个固定模式"。如果题目反过来——给一个长串，要找所有出现过两次以上的固定长度子串？这就引到 §4.1 的 LC 187。

4. 例题

4.1 LC 187 重复的 DNA 序列

链接：LeetCode 187

题意：给一个仅含 'A' 'C' 'G' 'T' 的字符串 s，返回所有长度为 10、在 s 中出现过两次或两次以上的子串（去重）。

数据范围：

1 ≤ len(s) ≤ 10⁵
仅含四种 DNA 字符

示例：

输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC", "CCCCCAAAAA"]

朴素思路：枚举每个长度 10 的子串，用 hashset 计数，再把出现次数 ≥ 2 的输出。子串切片本身 O(10)，总 O(10n)，能过。

哈希思路：把每个长度 10 子串映射成一个整数，用 set 记录见过的整数。第二次见到就加入答案集合。可以用滚动哈希让每次更新 O(1)，省掉字符串切片。

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> list[str]:
        n = len(s)
        if n < 10:
            return []
        base, mod = 5, 10 ** 9 + 7              # 字符集 4 个字符，base 取 5 够用
        K = 10                                    # 子串长度
        power = pow(base, K - 1, mod)             # base^(K-1)
        h = 0
        for i in range(K):
            h = (h * base + ord(s[i])) % mod
        seen = {h}
        added = set()                             # 已加入答案的子串（去重）
        for i in range(1, n - K + 1):
            # 滚动：减首位、乘 base、加尾
            h = ((h - ord(s[i - 1]) * power) * base + ord(s[i + K - 1])) % mod
            if h in seen and s[i:i + K] not in added:
                added.add(s[i:i + K])
            else:
                seen.add(h)
        return list(added)

复杂度 O(n)。空间 O(n)——seen 最多 n - 9 个整数。

几个细节：

字符集小，base 不用太大：DNA 只 4 个字符，base = 5 就够；用 131 浪费精度。
碰撞验证：上面 s[i:i + K] not in added 已经做了字符串去重，避免两个不同子串撞同一个哈希被误判。
滚动公式：(h - s[i-1] * power) * base + s[i+K-1]——踢掉最高位、整体左移一位、加上新最低位。

位编码版（更快的工程实现）：

DNA 只有 4 个字符，可以用 2 bit 编一个字符，10 个字符就是 20 bit，全部塞进一个 int。每次滚动是位运算，比模乘更快：

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> list[str]:
        if len(s) < 10:
            return []
        m = {'A': 0, 'C': 1, 'G': 2, 'T': 3}
        mask = (1 << 20) - 1                      # 保留低 20 位
        h = 0
        for i in range(10):
            h = (h << 2) | m[s[i]]
        seen, ans = {h}, set()
        for i in range(10, len(s)):
            h = ((h << 2) | m[s[i]]) & mask
            if h in seen:
                ans.add(s[i - 9:i + 1])
            else:
                seen.add(h)
        return list(ans)

位编码版常数比模乘版小很多——位运算（左移 + 或 + 与掩码）单步 1-2 ns，而模乘单步 5-10 ns，DNA 这种 4 字母小字母表实测能差 2-4 倍。是 LC 187 这种"字符集很小、长度固定"题的工业级写法。

Follow-up：上面定长 10 子串、扫一遍。如果题目改成"找一个任意长度的最长重复子串"呢？

4.2 LC 1044 最长重复子串

链接：LeetCode 1044

题意：给一个字符串 s，找出出现至少两次的子串中最长的那个（任意一个即可）。如果不存在返回空串。

数据范围：

2 ≤ len(s) ≤ 3 × 10⁴
全是小写英文字母

示例：

输入：s = "banana"
输出："ana"
解释："ana" 在下标 1 和 3 各出现一次，是最长重复子串。

关键观察：答案长度 L 满足单调性——如果存在长度为 L 的重复子串，那任何 L' ≤ L 都存在（取那条重复子串的前缀就是）。所以可以二分长度 L，每次判断"存在长度为 L 的重复子串吗"。

判定子问题：长度 L 固定后，问题变成 LC 187 的推广——把 s 中所有长度 L 的子串哈希记进 set，看有没有撞上的。O(n)。

整体 O(n log n)。

class Solution:
    def longestDupSubstring(self, s: str) -> str:
        n = len(s)
        base, mod = 131, (1 << 61) - 1            # 2^61 - 1 是 Mersenne 质数，更难碰撞
        # 预处理前缀哈希
        h = [0] * (n + 1)
        p = [1] * (n + 1)
        for i, ch in enumerate(s):
            h[i + 1] = (h[i] * base + ord(ch)) % mod
            p[i + 1] = p[i] * base % mod

        def get(l: int, r: int) -> int:
            return (h[r] - h[l] * p[r - l]) % mod

        def check(L: int) -> int:
            # 存在长度 L 的重复子串？返回某次出现的起点，否则 -1
            seen = {}
            for i in range(n - L + 1):
                key = get(i, i + L)
                if key in seen:
                    # 碰撞验证：起点对应字符比较
                    j = seen[key]
                    if s[i:i + L] == s[j:j + L]:
                        return i
                else:
                    seen[key] = i
            return -1

        lo, hi = 1, n - 1
        start, length = -1, 0
        while lo <= hi:
            mid = (lo + hi) // 2
            pos = check(mid)
            if pos >= 0:
                start, length = pos, mid          # 记录这次成功
                lo = mid + 1                       # 试更长
            else:
                hi = mid - 1                       # 试更短
        return s[start:start + length] if length > 0 else ""

复杂度：二分 O(log n) 层，每层 O(n)，总 O(n log n)。空间 O(n)。

关键细节：

Mersenne 质数 2⁶¹ - 1：10⁹ + 7 也行，但 LC 1044 评测数据偏大、单哈希 10⁹+7 有少数 case 会撞。2⁶¹ - 1 ≈ 2.3 × 10¹⁸ 比 10⁹+7 大约 9 个数量级，相应碰撞率小 9 个数量级；配合 Python 大整数 / Java long 都能跑。
碰撞验证不可省：check 里命中后做 s[i:i+L] == s[j:j+L] 字符比较。否则单哈希被构造数据卡的概率不低。L 越大越要验，因为 L 大的子串数量少、撞概率反而集中。
二分边界：lo = 1, hi = n - 1。最坏情况整个 s 都是同一个字符（"aaaa"），最长重复子串长度 n - 1。

用 KMP 行不行？——不行。KMP 是"在一个串里找另一个固定串"，这里固定串本身是要枚举的。可以用后缀数组在 O(n log n) 解，但代码量大 5 倍。哈希 + 二分是工程上最划算的解法。

Follow-up：上面是"在单串里找重复子串"。如果题目变成"两个串里找最长公共子串"、"DP 解 vs 哈希解的比较"、或者"给定哈希值反查子串"呢？——见 §6。

5. 边界、易错与复杂度

base 和 mod 怎么选

场景	推荐
LC 普通题（`n ≤ 10⁴`）	单哈希 `base = 131, mod = 10⁹+7`
LC 大数据题（`n ≥ 10⁵`）	单哈希 `base = 131, mod = (1 << 61) - 1`
竞赛 / 被构造数据卡过	双哈希 `(131, 10⁹+7) + (137, 10⁹+9)`
字符集极小（DNA, 二进制）	位编码（2~3 bit/字符）+ 滑窗 `&` mask

base 必须大于字符集大小——否则 "ab" 和 "ba" 都能哈希到同一个数。base 与 mod 互质（mod 是质数时自动满足）。

负数取模

Python % 对负数返回非负余数，可以直接 (a - b) % p。Java / C++ / Go 必须写 ((a - b) % p + p) % p，不然 h[l] * p[r-l] 比 h[r] 大时结果为负。

实现细节上，C++ 也能用 unsigned long long 让减法自然 wrap-around，但要小心：mod 为质数时 wrap 后结果不再正确，必须显式 + mod。

碰撞验证

单哈希 LC 上有概率 WA，但几乎所有题加一行字符比较就稳过：

if H.get(i, i + m) == nh and s[i:i + m] == needle:
    ...

哈希值命中频率本来就 1/p，多这一步常数代价微乎其微。提一句"hash check + char compare"两段式，是严谨写法。

双哈希写法

把模板的 (base, mod) 改成 ((base1, mod1), (base2, mod2))，所有 h 和 p 都开两套，比较时比较两个整数对：

class DoubleHash:
    def __init__(self, s):
        self.h1 = StringHash(s, 131, 10**9 + 7)
        self.h2 = StringHash(s, 137, 10**9 + 9)
    def get(self, l, r):
        return (self.h1.get(l, r), self.h2.get(l, r))   # 返回元组