Part 6.5：字符串哈希——O(1) 比较子串的利器

引言：当字符串比较成为瓶颈

在字符串处理中，我们经常面临一个基本操作：判断两个子串是否相等。一个朴素的方法是逐一比较字符，如果子串长度为 L，这个操作的时间复杂度就是 O(L)。当我们需要进行海量比较时，例如在一个长文本中查找一个模式串（KMP 解决的问题之一），或者寻找重复出现的子串时，这种 O(L) 的比较成本会迅速累积，成为性能瓶颈。

有没有办法能让我们以 O(1) 的时间复杂度判断两个子串是否相等呢？

答案是肯定的，这就是字符串哈希 (String Hashing) 的威力所在。其核心思想是：将每个字符串（或子串）映射成一个整数。之后，我们不再需要比较整个字符串，只需比较它们对应的哈希值即可。如果哈希值不同，那么字符串一定不同；如果哈希值相同，我们则大概率认为它们是相同的。

这种技术是著名的 Rabin-Karp 算法的核心，它不仅能用于字符串匹配，还能在许多其他字符串问题中大放异彩。

核心思想：把字符串变成数字

字符串哈希最经典的方法是多项式哈希 (Polynomial Hashing)。其思想是，选定一个基数 base 和一个**模数 mod**，将一个长度为 L 的字符串 S 看作一个 base 进制的数。

例如，对于字符串 "abc"，我们可以将其看作：
hash("abc") = (a * base² + b * base¹ + c * base⁰) mod mod

为了方便计算，我们通常将字符映射成一个大于 0 的整数。例如，'a' -> 1, 'b' -> 2, ...。

公式定义：对于字符串 S = s₁s₂...sₗ，其哈希值为：
H(S) = (s₁ * base^(L-1) + s₂ * base^(L-2) + ... + sₗ * base⁰) mod mod

如何高效计算子串哈希值？

如果我们想计算一个长字符串 T 中所有子串的哈希值，朴素地为每个子串都套用上述公式，效率依然很低。我们需要一种更智能的方法。

答案是**预计算前缀哈希 (Prefix Hashing)**。

我们定义 H[i] 为字符串 T 的前缀 T[1...i] 的哈希值。即：
H[i] = (T₁ * base^(i-1) + T₂ * base^(i-2) + ... + Tᵢ * base⁰) mod mod

这个 H 数组可以在 O(N) 的时间内计算出来，递推公式为：
H[i] = (H[i-1] * base + Tᵢ) mod mod

同时，我们还需要预计算 base 的幂次方，P[i] = baseⁱ mod mod。

有了这两个预计算数组，我们就可以在 O(1) 时间内计算出任意子串 T[i...j] 的哈希值！

子串 T[i...j] 的哈希值可以通过 H[j] 和 H[i-1] 推导出来：
H(T[1...j]) = H(T[1...i-1]) * base^(j-i+1) + H(T[i...j])

移项可得：
H(T[i...j]) = (H[j] - H[i-1] * P[j-i+1]) mod mod

注意，由于减法可能出现负数，在编程实现时需要处理成 (H[j] - H[i-1] * P[j-i+1] % mod + mod) % mod。

哈希冲突与对策

哈希的核心问题是**哈希冲突 (Hash Collision)**：两个不同的字符串可能拥有相同的哈希值。这就像我们不能仅凭身份证号的最后一位来断定两个人是同一个人一样。

如何选择 base 和 mod？

为了尽可能地减少冲突概率，base 和 mod 的选择至关重要：

1. **base (基数)**：应选择一个大于字符集大小的素数。例如，如果只考虑小写字母，字符集大小为 26，那么 base 可以选 31、37 等。常用的一个值是 131 或 13331。
2. **mod (模数)**：应选择一个足够大的素数，以降低冲突概率。常用的模数有 10^9 + 7, 10^9 + 9，或者 2^64 (此时可以利用 unsigned long long 的自然溢出，省去取模操作，速度更快)。

终极对策：双哈希 (Double Hashing)

即便我们精心挑选了 base 和 mod，在面对精心构造的数据时，依然可能发生冲突。为了让哈希几乎不可能被卡掉，我们可以采用双哈希或多哈希策略。

方法很简单：使用两组不同的 (base, mod) 来计算两个独立的哈希值。当且仅当两个字符串的两组哈希值都完全相等时，我们才认为这两个字符串是相同的。这极大地降低了冲突的概率。

Python 实现

下面是一个使用双哈希实现的字符串哈希模板，它可以 O(1) 查询任意子串的哈希值。

class StringHasher:
    def __init__(self, s: str):
        self.s = s
        n = len(s)

        # --- 双哈希配置 ---
        self.BASE1, self.MOD1 = 131, 10**9 + 7
        self.BASE2, self.MOD2 = 13331, 10**9 + 9

        # --- 预计算幂次方 ---
        self.pow1 = [1] * (n + 1)
        self.pow2 = [1] * (n + 1)
        for i in range(1, n + 1):
            self.pow1[i] = (self.pow1[i-1] * self.BASE1) % self.MOD1
            self.pow2[i] = (self.pow2[i-1] * self.BASE2) % self.MOD2

        # --- 预计算前缀哈希 ---
        self.h1 = [0] * (n + 1)
        self.h2 = [0] * (n + 1)
        for i in range(n):
            # 将字符映射为 1-26
            char_val = ord(s[i]) - ord('a') + 1 
            self.h1[i+1] = (self.h1[i] * self.BASE1 + char_val) % self.MOD1
            self.h2[i+1] = (self.h2[i] * self.BASE2 + char_val) % self.MOD2

    def get_hash(self, l: int, r: int) -> tuple[int, int]:
        """获取闭区间 [l, r] 的子串哈希值 (0-indexed)"""
        length = r - l + 1
        # 计算第一组哈希值
        hash1 = (self.h1[r+1] - self.h1[l] * self.pow1[length] % self.MOD1 + self.MOD1) % self.MOD1
        # 计算第二组哈希值
        hash2 = (self.h2[r+1] - self.h2[l] * self.pow2[length] % self.MOD2 + self.MOD2) % self.MOD2
        return (hash1, hash2)

# --- 案例：查找字符串中所有长度为 L 的重复子串 ---
def find_duplicate_substrings(s: str, L: int):
    n = len(s)
    if n < L:
        return

    hasher = StringHasher(s)
    seen = {}
    result = set()

    for i in range(n - L + 1):
        sub_hash = hasher.get_hash(i, i + L - 1)
        if sub_hash in seen:
            result.add(s[i : i + L])
        seen[sub_hash] = i
    
    print(f"在 '{s}' 中找到长度为 {L} 的重复子串: {result}")

# --- 测试 ---
find_duplicate_substrings("abacaba", 3)  # {'aba'}
find_duplicate_substrings("banana", 2)   # {'an', 'na'}
find_duplicate_substrings("mississippi", 4) # {'issi'}

复杂度分析

• 预处理时间复杂度: O(N)，其中 N 是字符串的长度。我们需要遍历一次字符串来计算前缀哈希和幂次方。
• 查询时间复杂度: O(1)。计算任意子串的哈希值只需要几次数学运算。
• 空间复杂度: O(N)。我们需要存储幂次方数组和前缀哈希数组。

经典应用

1. Rabin-Karp 字符串匹配：在一个长文本中查找一个模式串。计算出模式串的哈希值，然后用一个滑动窗口在文本串上移动，计算窗口内子串的哈希值并进行比较。时间复杂度可以达到 O(N+M)。
2. 查找最长重复子串：这是一个经典问题。我们可以二分答案（二分重复子串的长度 L），然后对于每个 L，使用字符串哈希检查是否存在长度为 L 的重复子串。总时间复杂度为 O(N log N)。
3. 最长回文子串：虽然 Manacher 是 O(N) 的最优解，但字符串哈希也提供了一种 O(N log N) 的简单思路。我们可以将原串 S 和其反转串 S_rev 拼接起来，然后用哈希快速判断 S 中的某个子串是否与其在 S_rev 中对称位置的子串相等。

总结

字符串哈希是一种用空间换时间的经典算法思想。它将复杂的字符串比较问题，通过数学映射，转化为了简单的整数比较问题，从而实现了 O(1) 的子串比较。

本文核心要点

✅ 核心思想：将字符串映射为整数，通过比较整数来代替比较字符串。
✅ 关键技术：利用前缀哈希，实现 O(1) 时间计算任意子串的哈希值。
✅ 公式：H(T[i...j]) = (H[j] - H[i-1] * P[j-i+1]) mod mod。
✅ 冲突处理：选择合适的 base 和 mod，并使用双哈希来极大地降低冲突概率。
✅ 应用广泛：是 Rabin-Karp、最长重复子串等多种字符串问题的基础。

虽然字符串哈希是一种随机化算法（存在理论上的冲突可能），但在算法竞赛和工程实践中，只要哈希函数设计得当，它就是解决许多字符串难题的一把瑞士军刀。