在许多数据结构与算法（DSA）问题中，我们经常需要处理字符串比较的任务——无论是想在句子中查找某个单词，检测重复内容，还是在一段大文本中寻找特定模式。
这就好比我们要在一个庞大的段落里找一句短语——如果人工逐字逐句地去检查，那将会非常枯燥且累人。计算机做同样的事情时，如果不讲究方法，处理长文本的速度也会变得非常慢。
这正是 Rabin-Karp 算法大显身手的地方。
该算法由 Michael Rabin 和 Richard Karp 于 1987 年提出，这是一种利用哈希技术来加速模式匹配的巧妙方法。它不再逐个字符地比对，而是将字符串转化为数字（哈希值）进行比较——就像商店里使用条形码来扫描商品，而不是读取完整的产品名称一样。
简而言之，Rabin-Karp 算法具有以下特点：
- 一种高效的字符串匹配算法
- 使用滚动哈希在文本中查找所有出现的模式
- 针对多模式或需要重复匹配的场景进行了优化
这构成了现代抄袭检测、子串搜索等许多算法的基础。
为什么我们需要 Rabin-Karp 算法？
假设我们要在一篇很长的文章中查找单词 "code" 是否出现。
最简单的方法是什么？从第一个字母开始，每次检查一组 4 个字母。这就是我们所说的朴素方法，它确实有效——但每次都要检查每个字符，如果文本很长，效率会非常低。
朴素方法的时间复杂度是 O(n × m)，其中：
- n = 文本的长度
- m = 模式（Pattern）的长度
现在想象一下，如果我们需要查找多个模式（比如在文档中检查 100 个不同的单词）。使用朴素方法来做这件事，速度会慢到让人难以忍受。
Rabin-Karp 算法通过使用滚动哈希改进了这一点。
它不再每次都对比实际的字符，而是将模式和文本的各个部分都转化为数字（哈希值）并比较这些数字。这样，大部分情况下它无需查看每个字符就能检测到不匹配，使得算法速度更快且扩展性更强。
Rabin-Karp 算法的核心思想
Rabin-Karp 算法背后的主要思想是将字符串转换为数值哈希，这样我们就可以通过比较数字来代替比较字符。这大大加快了处理速度。
为了高效地做到这一点，我们使用滚动哈希。它允许我们通过更新前一个哈希值，在常数时间内计算出下一个子串的哈希值。因此，我们不需要重新检查每个字符，只需滑动窗口并调整哈希值即可。
我们首先计算模式的哈希值，然后将其与文本中所有子串的哈希值进行比较。如果哈希值匹配，为了确认（为了避免哈希冲突导致的误差），我们会快速地执行一次逐字符检查。
通过这种方式，大多数比较都是通过数字完成的，这使得模式匹配变得快速且可扩展，特别是对于大文本或多个模式的情况。
#### Rabin-Karp 算法如何计算哈希值？
Rabin-Karp 算法中的哈希值是通过滚动哈希函数计算得出的，这允许我们在模式滑过文本时高效地更新哈希值。不需要为每个子串重新计算整个哈希，滚动哈希让我们可以在常数时间内移除旧字符的贡献并加上新字符。
字符串通过多项式滚动哈希转换为数值哈希。对于长度为 n 的字符串 s，哈希值计算如下：
=> hash(s) = (s[0] p^(n-1) + s[1] p^(n-2) + … + s[n-1] * p^0 ) % mod
其中：
- s[i] 是第 i 个字符的数值（‘a‘ = 1, ‘b‘ = 2, …, ‘z‘ = 26）
- p 是一个小质数（通常为 31 或 37）
- mod 是一个大质数（如 1e9 + 7），用于避免溢出并减少哈希冲突
这种方法允许我们利用预计算的幂和前缀哈希，在常数时间内计算子串的哈希值。
#### 哈希递推关系
设 preHash[i] 表示前缀子串 s[0…i] 的哈希值。
那么递推关系为：preHash[i] = preHash[i – 1] * base + s[i]
其中：
- preHash[0] = s[0]
- s[i] 是第 i 个字符的数值（‘a‘ = 1, ‘b‘ = 2, …, ‘z‘ = 26）
- base 是一个选定的质数（通常为 31 或 37）
- 所有运算都在模 mod 下进行，以避免溢出
#### 如何计算 L 到 R 的哈希值？
为了高效地获取任意子串 s[L…R] 的哈希值，我们可以使用前缀哈希。
首先，我们预计算前缀哈希，其中 prefix[i] 存储子串 s[0…i] 的哈希值。同时，我们也预计算 base 的幂（如 base^1, base^2 等）以帮助快速计算。
然后，利用模运算，我们可以在常数时间内计算出任意范围的哈希值。
实战示例：深入理解
让我们通过一个具体的例子来理解 Rabin-Karp 算法的工作原理。
假设我们有以下输入：
- 文本: "GEEKS FOR GEEKS"
- 模式: "GEEK"
步骤 1：计算模式的哈希值
首先，我们需要计算模式 "GEEK" 的哈希值。让我们使用简单的哈希函数，其中每个字符的值是其字母顺序（A=1, B=2, …, Z=26），不使用模运算以便于理解（实际实现中必须使用模运算）。
hash("GEEK") = 7 10^3 + 5 10^2 + 5 10^1 + 11 10^0 = 7000 + 500 + 50 + 11 = 7561
步骤 2：计算文本中第一个窗口的哈希值
接下来，计算文本中第一个与模式长度相同的子串的哈希值。
第一个窗口是 "GEEK"（与模式相同）：
hash("GEEK") = 7 10^3 + 5 10^2 + 5 10^1 + 11 10^0 = 7561
由于模式哈希和第一个窗口哈希相同，我们进行逐字符比较，确认匹配。
步骤 3：滑动窗口并更新哈希值
现在，我们将窗口向右滑动一个字符，计算下一个窗口的哈希值。我们可以利用前一个窗口的哈希值来计算新的哈希值，而不需要重新计算整个窗口。
下一个窗口是 "EEKS"。我们可以通过以下公式计算新哈希值：
新哈希值 = (旧哈希值 – 移除字符的贡献) * 基数 + 新字符的贡献
hash("EEKS") = (7561 – 7 10^3) 10 + 19 10^0 = (7561 – 7000) 10 + 19 = 561 * 10 + 19 = 5610 + 19 = 5629
比较 5629 与模式哈希值 7561，它们不相同，所以这个窗口不匹配。
步骤 4：继续滑动窗口
我们继续滑动窗口并更新哈希值，直到找到所有匹配的位置。
Rabin-Karp 算法的实现
下面是 Rabin-Karp 算法的 Python 实现：
def rabin_karp_search(text, pattern):
n = len(text)
m = len(pattern)
# 基数和模数
base = 256 # 字符集大小
prime = 101 # 一个质数
# 计算基数^(m-1)用于滚动哈希
h = 1
for i in range(m - 1):
h = (h * base) % prime
# 计算模式和文本第一个窗口的哈希值
pattern_hash = 0
text_hash = 0
for i in range(m):
pattern_hash = (base * pattern_hash + ord(pattern[i])) % prime
text_hash = (base * text_hash + ord(text[i])) % prime
# 滑动窗口遍历文本
for i in range(n - m + 1):
# 检查哈希值是否匹配
if pattern_hash == text_hash:
# 哈希值匹配，进行逐字符比较
match = True
for j in range(m):
if text[i + j] != pattern[j]:
match = False
break
if match:
print(f"模式出现在索引 {i}")
# 计算下一个窗口的哈希值
if i < n - m:
text_hash = (base * (text_hash - ord(text[i]) * h) + ord(text[i + m])) % prime
# 确保text_hash为正数
if text_hash < 0:
text_hash += prime
# 示例使用
text = "GEEKS FOR GEEKS"
pattern = "GEEK"
rabin_karp_search(text, pattern)
Rabin-Karp 算法的局限性
虽然 Rabin-Karp 算法在许多情况下表现良好，但它也有一些局限性：
- 哈希冲突：不同的字符串可能具有相同的哈希值，导致误报。虽然我们可以通过逐字符比较来确认匹配，但这会降低性能。
- 最坏情况时间复杂度：在哈希冲突频繁的情况下，算法的时间复杂度可能退化到 O(n × m)，与朴素算法相同。
- 内存使用：为了计算哈希值，我们需要存储一些额外的数据，如前缀哈希和基数的幂。
为什么需要双重哈希？
为了减少哈希冲突的概率，我们可以使用双重哈希。这意味着我们使用两个不同的哈希函数计算两个不同的哈希值，只有当两个哈希值都匹配时，我们才认为可能匹配。
def rabin_karp_double_hash(text, pattern):
n = len(text)
m = len(pattern)
# 两个不同的基数和模数
base1, base2 = 256, 257
prime1, prime2 = 101, 103
# 计算基数^(m-1)用于滚动哈希
h1, h2 = 1, 1
for i in range(m - 1):
h1 = (h1 * base1) % prime1
h2 = (h2 * base2) % prime2
# 计算模式和文本第一个窗口的哈希值
pattern_hash1, pattern_hash2 = 0, 0
text_hash1, text_hash2 = 0, 0
for i in range(m):
pattern_hash1 = (base1 * pattern_hash1 + ord(pattern[i])) % prime1
pattern_hash2 = (base2 * pattern_hash2 + ord(pattern[i])) % prime2
text_hash1 = (base1 * text_hash1 + ord(text[i])) % prime1
text_hash2 = (base2 * text_hash2 + ord(text[i])) % prime2
# 滑动窗口遍历文本
for i in range(n - m + 1):
# 检查两个哈希值是否都匹配
if pattern_hash1 == text_hash1 and pattern_hash2 == text_hash2:
# 哈希值匹配，进行逐字符比较
match = True
for j in range(m):
if text[i + j] != pattern[j]:
match = False
break
if match:
print(f"模式出现在索引 {i}")
# 计算下一个窗口的哈希值
if i < n - m:
text_hash1 = (base1 * (text_hash1 - ord(text[i]) * h1) + ord(text[i + m])) % prime1
text_hash2 = (base2 * (text_hash2 - ord(text[i]) * h2) + ord(text[i + m])) % prime2
# 确保哈希值为正数
if text_hash1 < 0:
text_hash1 += prime1
if text_hash2 < 0:
text_hash2 += prime2
# 示例使用
text = "GEEKS FOR GEEKS"
pattern = "GEEK"
rabin_karp_double_hash(text, pattern)
Rabin-Karp 算法适用的题型
Rabin-Karp 算法特别适用于以下类型的题目：
- 多模式匹配：当需要在文本中查找多个模式时，Rabin-Karp 可以预先计算所有模式的哈希值，然后一次性扫描文本。
- 子串搜索：如查找一个字符串是否是另一个字符串的子串。
- 重复检测：如检测文档中的重复内容或抄袭。
- 二维模式匹配：Rabin-Karp 算法也可以扩展到二维模式匹配，如在图像中查找特定模式。
性能优化建议
- 选择合适的基数和模数：基数通常选择字符集的大小，而模数应选择一个较大的质数以减少冲突。
- 避免哈希冲突：使用双重哈希或更复杂的哈希函数可以显著减少冲突。
- 预计算：预先计算基数的幂可以加速哈希值的计算。
常见错误和解决方案
- 整数溢出：在计算哈希值时，如果基数和模数选择不当，可能导致整数溢出。解决方案是使用大质数作为模数，并在每一步进行模运算。
- 负数哈希值：在更新哈希值时，可能会出现负数。解决方案是确保哈希值始终为正数，可以通过加上模数来实现。
结论
Rabin-Karp 算法是一种强大的字符串匹配技术，它通过哈希技术将字符串比较转化为数字比较，从而提高了效率。虽然在最坏情况下时间复杂度与朴素算法相同，但在平均情况下，特别是在多模式匹配场景中，它表现出了优越的性能。通过合理选择哈希函数和优化实现细节，我们可以充分利用 Rabin-Karp 算法解决各种字符串匹配问题。
实用的后续步骤
- 实现你自己的版本：尝试用不同的编程语言实现 Rabin-Karp 算法，并测试不同的哈希函数。
- 性能测试：比较 Rabin-Karp 算法与其他字符串匹配算法（如 KMP）在不同输入下的性能。
- 应用场景：探索 Rabin-Karp 算法在实际项目中的应用，如搜索功能、数据验证等。
通过这篇文章，我们深入探讨了 Rabin-Karp 算法的原理、实现和应用。希望这能帮助你更好地理解和应用这一算法。