什么是 Rabin–Karp 算法？使用 Rolling Hash 进行字符串匹配

Rabin–Karp 是一种经典的字符串匹配算法，用于在 Text 中查找 Pattern。

与每个位置都逐字符比较不同，它先计算 Pattern 的 Hash，然后与 Text 中相同长度 Window 的 Hash 进行比较。

核心思想是：

先比较 Hash，只有 Hash 相同时才进行精确字符串比较。

Rolling Hash

如果当前 Window 是：

ABC

下一个 Window 是：

BCD

我们不需要重新计算整个 BCD 的 Hash。

可以从旧 Hash 中移除 A 的贡献，然后加入 D。

这种技术称为 Rolling Hash。

Hash Collision

不同字符串可能产生相同的 Hash。

因此算法必须执行：

Hash Match
↓
Exact Character Comparison
↓
Real Match or Collision

不能把 Hash 相等直接当作字符串相等。

Polynomial Rolling Hash

字符串可以用多项式形式表示：

A × base² + B × base + C

再使用 Prime Modulo 控制数值大小。

TypeScript 实现

function rabinKarp(
  text: string,
  pattern: string
): number {
  const n = text.length;
  const m = pattern.length;

  if (m === 0) return 0;
  if (m > n) return -1;

  const base = 256;
  const prime = 101;

  let patternHash = 0;
  let windowHash = 0;
  let highOrder = 1;

  for (let i = 0; i < m - 1; i++) {
    highOrder = (highOrder * base) % prime;
  }

  for (let i = 0; i < m; i++) {
    patternHash = (
      base * patternHash + pattern.charCodeAt(i)
    ) % prime;

    windowHash = (
      base * windowHash + text.charCodeAt(i)
    ) % prime;
  }

  for (let i = 0; i <= n - m; i++) {
    if (
      patternHash === windowHash &&
      text.slice(i, i + m) === pattern
    ) {
      return i;
    }

    if (i < n - m) {
      windowHash = (
        base * (
          windowHash -
          text.charCodeAt(i) * highOrder
        ) +
        text.charCodeAt(i + m)
      ) % prime;

      if (windowHash < 0) {
        windowHash += prime;
      }
    }
  }

  return -1;
}

复杂度

平均情况下：

O(n + m)

如果发生大量 Collision，最坏情况可能达到：

O(n × m)

标准单 Pattern 实现的额外空间约为：

O(1)

与 KMP 的区别

KMP 使用 Prefix、Suffix 和 LPS 数组，并保证 O(n + m)。

Rabin–Karp 使用 Hashing 和 Rolling Hash，平均性能很好，但最坏情况可能受 Collision 影响。

多 Pattern 搜索

如果有很多相同长度的 Pattern，可以把它们的 Hash 存入 Set。

然后只需要检查每个 Text Window 的 Hash 是否存在于 Set 中，再对 Candidate 进行精确验证。

实际应用

Rolling Hash 的思想可以应用于：

• 字符串搜索
• Duplicate Detection
• Plagiarism Detection
• Document Fingerprinting
• DNA Sequence Search
• Repeated Substring
• Substring Queries

Double Hashing

使用两个不同的 Hash 和 Prime 可以显著降低 Collision 的概率。

只有两个 Hash 都匹配时才认为 Window 是 Candidate。

常见错误

• 只比较 Hash，不做精确验证。
• 每次重新计算整个 Window Hash。
• 忘记 Modulo。
• 使用较差的 Base 或 Prime。
• 错误地移除旧字符的高位贡献。

技术面试

Rabin–Karp 同时考察：

• Hashing
• Sliding Window
• Modular Arithmetic
• String Matching
• Collision Handling

理解 Rolling Hash 的更新过程比死记代码更重要。

总结

Rabin–Karp 的整体流程是：

Pattern → Hash

Text
↓
Sliding Window
↓
Rolling Hash
↓
Compare Hash
↓
Verify

最值得掌握的核心并不仅是 Pattern Search，而是 Rolling Hash：利用上一个 Window 的结果高效计算下一个 Window 的 Hash。