基于滚动哈希的字符串模式匹配：Rabin-Karp 算法详细解析
字数 2009 2025-12-06 02:32:14

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

1. 题目描述

给定一个文本字符串 text 和一个模式字符串 pattern，要求在文本中查找所有模式字符串出现的位置。你需要实现一个基于哈希的高效算法，在平均情况下达到近似线性时间复杂度，并能处理较长的文本和模式。

示例
输入：text = "abracadabra", pattern = "abra"
输出：[0, 7]（模式"abra"在文本中出现在索引0和索引7处）

2. 解题思路

常规的暴力匹配法需要 O(n·m) 的时间复杂度（n、m 分别为文本和模式长度）。Rabin-Karp 算法通过滚动哈希（Rolling Hash）将比较模式与子串的耗时从 O(m) 降为平均 O(1)，从而将整体时间复杂度优化到平均 O(n+m)。

核心思想

  1. 将模式字符串映射成一个哈希值（hash(pattern)）。
  2. 在文本中依次截取与模式等长的子串，计算其哈希值。
  3. 如果子串哈希值与模式哈希值相等，再逐字符验证（避免哈希冲突导致的误判）。
  4. 计算下一个子串哈希值时，利用上一个子串的哈希结果进行“滚动”更新，只需 O(1) 时间。

3. 详细步骤

步骤 1：选择哈希函数

Rabin-Karp 算法通常使用多项式滚动哈希（Polynomial Rolling Hash）。我们将字符串视为一个多进制数（基数 base，常取大质数，如 131、257 等），并对一个大质数（如 10^9+7）取模，以减少碰撞概率。

假设字符串 s 的长度为 m，字符 c 映射为整数（如 ASCII 值），则哈希值为：

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

其中 base 是进制基数，mod 是模数。

步骤 2：计算模式串的哈希值

以示例 pattern = "abra" 说明（为简化，此处用 ASCII 值，base=131, mod=10^9+7）：

  • 字符值：a=97, b=98, r=114, a=97
  • hash(pattern) = (97131^3 + 98131^2 + 114131^1 + 97131^0) mod mod

计算过程可迭代进行：

hash = 0
for char in pattern:
    hash = (hash * base + ord(char)) % mod

步骤 3：预计算 base 的幂

在滚动时，我们需要减去“离开字符”的贡献，这个贡献是 ord(离开字符) * base^(m-1)。因此需要预先计算 base^(m-1) % mod，记为 high_pow。

步骤 4：计算文本第一个子串的哈希值

取 text 前 m 个字符（m 为 pattern 长度），用同样方法计算初始哈希值。

步骤 5：滚动哈希

从 i=0 到 i=n-m（n 为 text 长度），依次处理：

  • 比较当前子串哈希值与模式哈希值。
  • 如果相等，则逐字符验证子串是否与 pattern 完全相同。
  • 将窗口右移一位：去掉最左字符，加入右边新字符，重新计算哈希值。

滚动更新公式（从子串 text[i..i+m-1] 到 text[i+1..i+m]）：

new_hash = ( (old_hash - ord(text[i]) * high_pow) * base + ord(text[i+m]) ) mod mod

注意：为避免负数，可先加 mod 再取模。

步骤 6：处理边界

当 i = n-m 时，已经是最后一个可能的子串，更新后不再需要继续滚动。

4. 完整示例

以 text="abracadabra", pattern="abra", base=131, mod=10^9+7 为例：

  1. 计算 pattern 哈希值：h_pattern = hash("abra") ≈ 某值 H。
  2. 计算 high_pow = base^(m-1) % mod = 131^3 % mod。
  3. 计算 text 第一个子串 "abra" 的哈希值 h = hash("abra")，与 H 相等，逐字符验证通过 → 记录索引 0。
  4. 滚动：
    • 从 "abra" 到 "brac"：h = ( (h - ord('a')high_pow) base + ord('c') ) % mod
    • 比较 h 与 H，不等，继续。
    • 重复直到结束，找到第二个匹配 "abra" 在索引 7。

5. 复杂度分析

  • 时间复杂度：计算 pattern 哈希 O(m)，预处理 high_pow O(log m)（快速幂），滚动 n-m+1 次，每次 O(1)。平均总时间 O(n+m)，最坏情况（大量哈希冲突）退化到 O(n·m)，但概率极低。
  • 空间复杂度：O(1)（除了存储结果）。

6. 关键点

  1. 哈希冲突：即使哈希值相等，也必须逐字符验证，确保结果正确。
  2. 参数选择：base 和 mod 应互质，mod 取大质数可减少碰撞。
  3. 滚动效率：核心优势在于用 O(1) 时间更新哈希，而不是每次重新计算 O(m)。

通过以上步骤，你可以实现一个高效的 Rabin-Karp 算法，用于在长文本中快速查找模式串的出现位置。

基于滚动哈希的字符串模式匹配：Rabin-Karp 算法详细解析 1. 题目描述 给定一个 文本字符串 text 和一个 模式字符串 pattern ，要求在文本中查找所有模式字符串出现的位置。你需要实现一个 基于哈希的高效算法 ，在平均情况下达到近似线性时间复杂度，并能处理较长的文本和模式。 示例 输入： text = "abracadabra" , pattern = "abra" 输出： [0, 7] （模式"abra"在文本中出现在索引0和索引7处） 2. 解题思路 常规的暴力匹配法需要 O(n·m) 的时间复杂度（n、m 分别为文本和模式长度）。Rabin-Karp 算法通过 滚动哈希 （Rolling Hash）将比较模式与子串的耗时从 O(m) 降为平均 O(1)，从而将整体时间复杂度优化到平均 O(n+m)。 核心思想 将模式字符串映射成一个哈希值（hash(pattern)）。 在文本中依次截取与模式等长的子串，计算其哈希值。 如果子串哈希值与模式哈希值相等，再 逐字符验证 （避免哈希冲突导致的误判）。 计算下一个子串哈希值时，利用上一个子串的哈希结果进行“滚动”更新，只需 O(1) 时间。 3. 详细步骤 步骤 1：选择哈希函数 Rabin-Karp 算法通常使用 多项式滚动哈希 （Polynomial Rolling Hash）。我们将字符串视为一个多进制数（基数 base，常取大质数，如 131、257 等），并对一个大质数（如 10^9+7）取模，以减少碰撞概率。 假设字符串 s 的长度为 m，字符 c 映射为整数（如 ASCII 值），则哈希值为： 其中 base 是进制基数，mod 是模数。 步骤 2：计算模式串的哈希值 以示例 pattern = "abra" 说明（为简化，此处用 ASCII 值，base=131, mod=10^9+7）： 字符值：a=97, b=98, r=114, a=97 hash(pattern) = (97 131^3 + 98 131^2 + 114 131^1 + 97 131^0) mod mod 计算过程可迭代进行： 步骤 3：预计算 base 的幂 在滚动时，我们需要减去“离开字符”的贡献，这个贡献是 ord(离开字符) * base^(m-1) 。因此需要预先计算 base^(m-1) % mod ，记为 high_pow 。 步骤 4：计算文本第一个子串的哈希值 取 text 前 m 个字符（m 为 pattern 长度），用同样方法计算初始哈希值。 步骤 5：滚动哈希 从 i=0 到 i=n-m（n 为 text 长度），依次处理： 比较当前子串哈希值与模式哈希值。 如果相等，则逐字符验证子串是否与 pattern 完全相同。 将窗口右移一位：去掉最左字符，加入右边新字符，重新计算哈希值。 滚动更新公式 （从子串 text[ i..i+m-1] 到 text[ i+1..i+m ]）： 注意：为避免负数，可先加 mod 再取模。 步骤 6：处理边界 当 i = n-m 时，已经是最后一个可能的子串，更新后不再需要继续滚动。 4. 完整示例 以 text="abracadabra", pattern="abra", base=131, mod=10^9+7 为例： 计算 pattern 哈希值：h_ pattern = hash("abra") ≈ 某值 H。 计算 high_ pow = base^(m-1) % mod = 131^3 % mod。 计算 text 第一个子串 "abra" 的哈希值 h = hash("abra")，与 H 相等，逐字符验证通过 → 记录索引 0。 滚动： 从 "abra" 到 "brac"：h = ( (h - ord('a') high_ pow) base + ord('c') ) % mod 比较 h 与 H，不等，继续。 重复直到结束，找到第二个匹配 "abra" 在索引 7。 5. 复杂度分析 时间复杂度：计算 pattern 哈希 O(m)，预处理 high_ pow O(log m)（快速幂），滚动 n-m+1 次，每次 O(1)。平均总时间 O(n+m)，最坏情况（大量哈希冲突）退化到 O(n·m)，但概率极低。 空间复杂度：O(1)（除了存储结果）。 6. 关键点 哈希冲突 ：即使哈希值相等，也必须逐字符验证，确保结果正确。 参数选择 ：base 和 mod 应互质，mod 取大质数可减少碰撞。 滚动效率 ：核心优势在于用 O(1) 时间更新哈希，而不是每次重新计算 O(m)。 通过以上步骤，你可以实现一个高效的 Rabin-Karp 算法，用于在长文本中快速查找模式串的出现位置。