字符串匹配算法：Rabin-Karp 算法原理与实现

1. 问题背景与描述

在字符串处理中，一个非常基础且重要的问题是：给定一个较长的文本字符串 text（长度为 n），和一个较短的模式字符串 pattern（长度为 m），找出 pattern 在 text 中所有出现的位置（起始索引）。这就是经典的字符串匹配问题。

最直观的方法是暴力匹配（Brute-Force），从 text 的第一个字符开始，依次比较 text[i...i+m-1] 和 pattern[0...m-1] 是否完全相等。这种方法的时间复杂度是 O(n*m)，在文本很长、模式也不短的情况下效率较低。

有没有一种方法，能让我们“快速”地判断 text 中的一个窗口子串是否与 pattern 相等，而不需要一个字符一个字符地比较呢？Rabin-Karp 算法正是基于这个思想，它利用哈希函数（Hash Function） 来加速比较过程。

2. 算法核心思想

Rabin-Karp 算法的核心思想可以概括为：

1. 计算模式字符串 pattern 的哈希值。
2. 计算文本字符串 text 中每个可能的长度为 m 的子串的哈希值（滑动窗口）。
3. 如果某个子串的哈希值与 pattern 的哈希值相等，我们就谨慎地认为找到了一个可能的匹配位置，然后再用逐字符比较来确认（因为哈希值可能冲突）。
4. 为了提高效率，我们不直接为每个子串独立计算哈希值，而是利用前一个子串的哈希值，通过一种巧妙的“滚动哈希（Rolling Hash）”技术，快速计算出下一个子串的哈希值。

3. 关键组件：滚动哈希

一个良好的滚动哈希函数是 Rabin-Karp 算法的精髓。它需要支持我们已知子串 text[i...i+m-1] 的哈希值 H_i，能快速计算出下一个子串 text[i+1...i+m] 的哈希值 H_{i+1}。

一种常用且简单有效的滚动哈希是多项式滚动哈希（Polynomial Rolling Hash），它把字符串看成一个某基数（base，通常是一个质数，如31， 101， 131等）下的多位数。

• 哈希计算：
  对于一个字符串 s（长度为 m），它的哈希值可以定义为：
  hash(s) = (s[0] * base^{m-1} + s[1] * base^{m-2} + ... + s[m-1] * base^{0}) mod modulus
  其中 modulus 是一个很大的质数（如 10^9+7），用来防止哈希值过大导致溢出，同时也能降低哈希冲突的概率。这里 s[k] 通常指的是字符的 ASCII 码值。

• 滚动更新（从 H_i 到 H_{i+1}）：
  假设我们刚计算完窗口 text[i...i+m-1] 的哈希值 H_i。
  窗口 text[i+1...i+m] 的哈希值 H_{i+1} 可以通过以下步骤快速得到：

  1. 从 H_i 中移除最高位（最左边）字符 text[i] 的贡献：remove = text[i] * base^{m-1}
  2. 将整个哈希值左移一位（相当于乘以 base）：(H_i - remove) * base
  3. 加上新进入窗口的最低位（最右边）字符 text[i+m] 的贡献（其幂次为 base^0）：((H_i - remove) * base + text[i+m]) mod modulus
     但是，在模运算下，步骤1中的 remove 计算需要注意取模的逆运算。更标准且无歧义的公式是：
     H_{i+1} = ((H_i - text[i] * highest_pow) * base + text[i+m]) mod modulus
     其中 highest_pow = base^{m-1} mod modulus，我们可以预先计算并保存这个值。

  这个计算过程是 O(1) 的，而暴力重新计算一个子串的哈希值是 O(m) 的。

4. 算法步骤详解

现在我们结合具体流程来讲解：

1. 初始化参数：

   • 选择一个基数 base（如 131）。
   • 选择一个模数 modulus（如 10^9+7），应足够大以减少冲突。
   • 计算 pattern 的哈希值 hash_pattern。
   • 计算 text 第一个长度为 m 的子串 text[0...m-1] 的哈希值 hash_window。
   • 预先计算 highest_pow = pow(base, m-1) mod modulus。通常通过快速幂算法计算。

2. 滑动窗口：

   • 循环遍历 text 中所有可能的起始位置 i，范围是从 0 到 n-m。
   • 对于每个位置 i：
     a. 哈希值比对：比较当前的 hash_window 与 hash_pattern。
     b. 确认匹配：如果哈希值相等，为了排除哈希冲突导致的假阳性匹配，必须使用逐字符比较 text[i...i+m-1] 和 pattern 来确认。只有完全相等，才记录位置 i 为一个有效匹配。
     c. 滚动更新哈希（如果 i < n-m）：
     使用公式计算下一个窗口的哈希值：
     hash_window = ((hash_window - text[i] * highest_pow) * base + text[i+m]) mod modulus
     为了保证结果非负，我们在做减法和取模时通常这样写：
     hash_window = ((hash_window - (text[i] * highest_pow) % modulus + modulus) % modulus) * base + text[i+m]) % modulus
     其中 (text[i] * highest_pow) % modulus 是移除的贡献，+ modulus 是为了防止减法产生负数。

5. 时间复杂度分析

• 预处理阶段：计算 hash_pattern、第一个 hash_window 和 highest_pow 的时间复杂度是 O(m)。
• 主循环阶段：总共需要滑动 n-m+1 ≈ n 次窗口。每次窗口的哈希值更新是 O(1)。因此，主循环的哈希操作是 O(n)。
• 逐字符比较：只在哈希值匹配时发生。假设发生了 k 次匹配（包括真的和假的），每次比较需要 O(m) 时间。在最坏情况下（例如，所有字符相同且哈希冲突频繁），k 可能接近 n，导致最坏时间复杂度为 O(n*m)。但在实际应用中，只要哈希函数和模数选择得当，冲突概率很低，k 会非常小，使得平均时间复杂度接近 O(n+m)。这是一个典型的“拉斯维加斯算法”风格，即算法结果总是正确的，但运行时间有概率性。

6. 代码实现示例 (Python)

def rabin_karp(text, pattern):
    n, m = len(text), len(pattern)
    if m == 0:
        return [0]  # 空模式匹配所有位置起始（按定义）
    if n < m:
        return []
    
    base = 131        # 基数
    modulus = 10**9 + 7 # 大质数模
    
    # 1. 计算最高位幂值 (base^(m-1) mod modulus)
    highest_pow = 1
    for _ in range(m - 1):
        highest_pow = (highest_pow * base) % modulus
    
    # 2. 计算模式串和第一个窗口的哈希值
    hash_pattern = 0
    hash_window = 0
    for i in range(m):
        # 计算模式串哈希
        hash_pattern = (hash_pattern * base + ord(pattern[i])) % modulus
        # 计算第一个窗口哈希
        hash_window = (hash_window * base + ord(text[i])) % modulus
    
    result = []
    
    # 3. 滑动窗口
    for i in range(n - m + 1):
        # 检查哈希值是否匹配
        if hash_window == hash_pattern:
            # 哈希匹配，进行逐字符确认
            if text[i:i+m] == pattern:
                result.append(i)
        
        # 如果不是最后一个窗口，滚动计算下一个窗口的哈希值
        if i < n - m:
            # 移除左边字符贡献，加上右边新字符贡献
            hash_window = ((hash_window - ord(text[i]) * highest_pow) * base + ord(text[i+m])) % modulus
            # 确保哈希值为非负数
            if hash_window < 0:
                hash_window += modulus
    
    return result

# 示例
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
print("匹配起始位置:", rabin_karp(text, pattern)) # 应输出 [10]

7. 算法特点与总结

• 优点：
  1. 平均情况下非常高效（O(n+m)），适合在长文本中搜索较短的、非高度重复的模式。
  2. 概念清晰，实现相对简单。
  3. 天然支持多模式匹配的扩展。可以同时计算多个模式的哈希值，然后用文本窗口的哈希值与这个集合进行比较，这在某些场景下比单跑多次算法更高效。
  4. 思想可以扩展到二维模式匹配等更复杂的问题。
• 缺点：
  1. 最坏情况时间复杂度退化为 O(n*m)（尽管概率极低）。
  2. 需要谨慎选择哈希参数（base, modulus）以平衡速度和冲突概率。
  3. 相比 KMP 或 Boyer-Moore 等算法，在最坏情况保证和常数因子优化上可能不占优势。

Rabin-Karp 算法巧妙地将字符串的相等比较转化为哈希值的比较，并通过滚动哈希实现了高效的滑动窗口更新，是理解哈希技术如何应用于非数值比较问题的一个绝佳范例。