多项式滚动哈希

多项式滚动哈希 (Polynomial Rolling Hash) 是一种常用于字符串匹配、重复子串查找等场景的字符串哈希算法。它的核心思想是将一个字符串看作是一个高进制的数字，并将其映射为一个整数（哈希值）。

通过巧妙的数学性质，它能够在 $O(1)$ 的时间内计算出任意子串的哈希值，从而极大地提高字符串处理的效率（例如在 Rabin-Karp 字符串匹配算法中）。

核心原理

对于一个长度为 $L$ 的字符串 $S = c_0 c_1 c_2 \dots c_{L-1}$，我们可以选择一个基数 (Base) $P$ 和一个模数 (Mod) $M$，将其转化为如下的多项式值：

$H(S) = \left( c_0 \cdot P^{L-1} + c_1 \cdot P^{L-2} + \dots + c_{L-1} \cdot P^0 \right) \pmod M$

其中：

• $c_i$：字符的数值（通常取其 ASCII 码，例如 'a' 为 1 或 97，为避免冲突建议从 1 开始）。
• $P$ (基数)：通常取一个大于字符集大小的质数（例如小写字母场景常取 $31$ 或 $131$）。
• $M$ (模数)：为了防止溢出并保证哈希值在安全范围内，通常取一个很大的质数（例如 $10^9 + 7$ 或 $10^9 + 9$）。

为什么叫“滚动”？

如果我们要暴力计算一个字符串所有子串的哈希值，复杂度会达到 $O(N^2)$。而滚动哈希的精髓在于递推：

假设已知子串 $S[i \dots j]$ 的哈希值为 $H$，当我们把窗口向右移动一位，去掉最左边的字符 $c_i$ 并加入右边的新字符 $c_{j+1}$ 时，我们不需要重新计算整个多项式，只需进行简单的数学运算：

1. 减去最高位字符的影响：$H - c_i \cdot P^{j-i}$
2. 整体向左进一位（乘以基数 $P$）：$\times P$
3. 加上新加入的最低位字符：$+ c_{j+1}$

这样，新子串的哈希值就可以在 $O(1)$ 时间 内计算出来。

代码实现

下面是一个使用多项式滚动哈希查找子串的简单实现：

def polynomial_rolling_hash(s, pattern):
    n, m = len(s), len(pattern)
    if n < m:
        return -1

    P = 131
    MOD = 10**9 + 7

    # 计算 P^(m-1) % MOD
    p_pow = 1
    for _ in range(m - 1):
        p_pow = (p_pow * P) % MOD

    # 计算 pattern 和 s 中第一个窗口的哈希值
    pattern_hash = 0
    current_hash = 0
    for i in range(m):
        pattern_hash = (pattern_hash * P + ord(pattern[i])) % MOD
        current_hash = (current_hash * P + ord(s[i])) % MOD

    if current_hash == pattern_hash:
        return 0

    # 滚动哈希滑动窗口
    for i in range(n - m):
        # 移除最高位，乘以 P，加上新最低位
        current_hash = (
            (current_hash - ord(s[i]) * p_pow) * P + ord(s[i + m])
        ) % MOD
        # Python 的求模对负数同样适用，但为了安全可以加上 MOD
        current_hash = (current_hash + MOD) % MOD

        if current_hash == pattern_hash:
            return i + 1

    return -1

优缺点与注意事项

优点

• 高效：预处理 $O(N)$，单次查询或滚动更新 $O(1)$。
• 实现简单：代码量少，常用于竞赛编程（如字符串哈希、最长回文子串、重复子串等）。

缺点与防范 (哈希碰撞)

• 理论上存在哈希碰撞的风险（即不同的字符串算出了相同的哈希值）。
• 应对策略：
  1. 使用双哈希（选用两组不同的 $P$ 和 $M$ 分别计算，两个都相等才认为字符串相同），将碰撞概率降到最低。
  2. 使用自然溢出（利用无符号 64 位整数溢出作为隐式取模），但需警惕精心构造的恶意碰撞数据。