基于滚动哈希的字符串模式匹配：Rabin-Karp 算法详细解析

题目描述
给定一个文本字符串 text 和一个模式字符串 pattern，请使用 Rabin-Karp 算法 在文本中查找所有模式串出现的位置。该算法通过滚动哈希（Rolling Hash）在常数时间内更新子串的哈希值，从而高效地比较文本中的连续子串与模式串。需要处理哈希冲突（即哈希值相同但字符串不同），并返回所有匹配的起始索引。

解题过程循序渐进讲解

步骤1：理解滚动哈希的核心思想

滚动哈希的核心是：当我们计算文本中一个长度为 m（模式串长度）的子串哈希值时，相邻子串的哈希值可以通过前一个子串的哈希值快速推导，而无需重新计算整个子串。

滚动哈希公式（以多项式哈希为例）：

• 假设字符串 s 的每个字符映射为一个数字（如 ASCII 码）。
• 选择一个基数 base（通常为质数，如 31、257）和一个模数 mod（通常为大质数，如 10^9+7）。
• 长度为 m 的子串哈希值定义为：

\[ hash(s[i:i+m]) = (s[i] \times base^{m-1} + s[i+1] \times base^{m-2} + \dots + s[i+m-1]) \bmod mod \]

• 从位置 i 到 i+1 的哈希滚动公式为：

\[ hash_{i+1} = (hash_i - s[i] \times base^{m-1}) \times base + s[i+m] \]

注意：需要处理取模运算中的负数（通过加 mod 再取模）。

步骤2：算法流程

1. 计算模式串的哈希值 hash_pattern 和文本中第一个长度为 m 的子串哈希值 hash_text。
2. 预计算 base^(m-1) mod mod 的值，用于滚动时移除首字符的贡献。
3. 从 i=0 到 n-m 遍历文本：
   • 比较当前子串哈希值 hash_text 与 hash_pattern。
   • 如果哈希值相等，逐字符比较子串与模式串（避免哈希冲突导致的误判）。
   • 如果匹配，记录起始索引 i。
   • 用滚动公式更新 hash_text 到下一个子串。
4. 返回所有匹配的起始索引列表。

步骤3：具体示例

假设：

• text = "abracadabra"，pattern = "abra"
• 映射规则：a=1, b=2, …, z=26（仅示例，实际用 ASCII 码）
• 取 base=31，mod=10007

计算模式串哈希：
"abra" → hash_pattern = (1×31³ + 2×31² + 18×31¹ + 1×31⁰) mod 10007 = 8074（示例值）

滚动过程：

1. 计算 text[0:4]="abra" 的哈希值，与 hash_pattern 相等 → 逐字符比较确认匹配 → 记录索引 0。
2. 滚动到 text[1:5]="brac"：用公式移除 'a'、加入 'c' 更新哈希值。
3. 继续直到文本末尾。
   最终匹配索引为 0 和 7。

步骤4：处理哈希冲突

哈希冲突指不同字符串具有相同哈希值。Rabin-Karp 算法的关键步骤是：当哈希值匹配时，必须逐字符验证子串是否与模式串真正相等。这保证了结果的绝对正确性，但最坏情况下（哈希频繁冲突）时间复杂度退化为 O(nm)。通过精心选择 base 和 mod（如使用双哈希）可降低冲突概率。

步骤5：时间与空间复杂度

• 时间复杂度：平均 O(n + m)，最坏 O(nm)（当所有子串哈希冲突时）。
• 空间复杂度：O(1)（除存储结果外无需额外空间）。

步骤6：代码框架（Python 示例）

def rabin_karp(text, pattern):
    n, m = len(text), len(pattern)
    if m == 0 or n < m:
        return []
    
    base, mod = 31, 10**9 + 7
    # 计算 base^(m-1) mod mod
    highest_pow = pow(base, m-1, mod)
    
    # 计算模式串和第一个子串的哈希值
    hash_pattern = 0
    hash_window = 0
    for i in range(m):
        hash_pattern = (hash_pattern * base + ord(pattern[i])) % mod
        hash_window = (hash_window * base + ord(text[i])) % mod
    
    res = []
    for i in range(n - m + 1):
        if hash_window == hash_pattern:
            # 逐字符验证避免冲突
            if text[i:i+m] == pattern:
                res.append(i)
        if i < n - m:
            # 滚动哈希：移除 text[i]，加入 text[i+m]
            hash_window = ((hash_window - ord(text[i]) * highest_pow) * base + ord(text[i+m])) % mod
            hash_window = (hash_window + mod) % mod  # 确保非负
    return res

总结
Rabin-Karp 算法通过滚动哈希实现了高效的模式匹配，特别适用于多模式搜索或流式数据匹配。其核心在于哈希值的快速更新和冲突时的安全验证。实际应用中可通过双哈希（两个不同模数）进一步减少冲突概率。