1. 概述
在计算机科学中，字符串搜索指的是在一个大文本中查找一个或多个字符串（称为模式串）的位置。
本文将讨论 Rabin-Karp 字符串搜索算法。我们将先介绍朴素的字符串搜索算法，然后解释 Rabin-Karp 算法，并通过一个示例演示其工作原理。
最后，我们还会讨论该算法的一些变体。
2. 朴素算法
2.1 伪代码
该算法的核心思想非常简单：它通过尝试从文本中的每一个可能位置开始匹配模式串来完成搜索。
以下是该算法的伪代码：
algorithm NaiveStringSearch(P, T):
// INPUT
// P = 要查找的模式串
// T = 要查找的文本
// OUTPUT
// 返回 P 在 T 中出现的次数
answer <- 0
n <- length(T)
k <- length(P)
for i <- 0 to n - k:
valid <- true
for j <- 0 to k - 1:
if T[i + j] != P[j]:
valid <- false
break
if valid = true:
answer <- answer + 1
return answer
我们尝试从文本 T 的每一个起始位置匹配模式串 P，只要发现字符不匹配就立即跳出循环。如果完全匹配，则计数器加一。
2.2 示例
假设我们要在 T = "ababaac" 中查找 P = "bab"，算法会按如下步骤执行：
| 起始位置 | 比较内容 | 匹配结果 |
|---|---|---|
| 0 | aba | ❌ |
| 1 | bab | ✅ |
| 2 | aba | ❌ |
| 3 | baa | ❌ |
| 4 | aac | ❌ |
**该算法的时间复杂度为 O(n * k)**，其中 n 是文本长度，k 是模式串长度。
3. Rabin-Karp 算法
要理解 Rabin-Karp 算法，我们首先需要了解哈希函数的工作原理。接下来我们再介绍算法本身。
3.1 哈希函数
为了提升效率，我们需要一个可以将字符串映射为整数的函数，称为哈希函数。我们希望：
- 哈希函数易于计算
- 可以通过预处理在 O(n) 时间内计算任意字符串的哈希值
- 可以在 O(1) 时间内计算任意子串的哈希值
3.2 哈希函数示例
最简单的哈希函数之一是将字符串中所有字符的 ASCII 码值相加：
algorithm HashStructureInit(s):
// 初始化前缀和数组
n <- length(s)
prefix[0] <- int(s[0])
for i <- 1 to n - 1:
prefix[i] <- prefix[i - 1] + int(s[i])
algorithm getHash(L, R):
// 获取子串的哈希值
if L = 0:
return prefix[R]
return prefix[R] - prefix[L - 1]
这个哈希函数虽然计算效率高，但存在较多哈希冲突（Collision），即不同字符串可能有相同的哈希值。
3.3 Rabin-Karp 核心思想
Rabin-Karp 的核心思想是：
- 使用哈希函数对文本和模式串进行预处理
- 在每个起始位置比较哈希值
- 如果哈希值不同，直接跳过；如果相同，再进行字符逐个比较
以下是 Rabin-Karp 的伪代码：
algorithm RabinKarpSearch(P, T, hashT, hashP):
answer <- 0
n <- length(T)
k <- length(P)
for i <- 0 to n - k:
textHash <- hashT.getHash(i, i + k - 1)
patternHash <- hashP.getHash(0, k - 1)
if textHash = patternHash:
valid <- true
for j <- 0 to k - 1:
if T[i + j] != P[j]:
valid <- false
break
if valid:
answer <- answer + 1
return answer
**最坏时间复杂度仍为 O(n * k)**，但若使用良好的哈希函数，期望复杂度可降低至 O(n + k * t)，其中 t 是匹配次数。
3.4 示例
我们再次以 T = "ababaac"，P = "bab" 为例：
| 起始位置 | 子串 | 哈希值 | 是否需要比较 | 结果 |
|---|---|---|---|---|
| 0 | aba | 292 | 否 | ❌ |
| 1 | bab | 293 | 是 | ✅ |
| 2 | aba | 292 | 否 | ❌ |
| 3 | baa | 292 | 否 | ❌ |
| 4 | aac | 293 | 是 | ❌ |
相比朴素算法，Rabin-Karp 只比较了 2 次，效率更高。
4. 更好的哈希函数
4.1 定义
为了减少哈希冲突，我们可以使用基于多项式滚动哈希的函数：
- 将字符串视为一个
B进制数，其中B是一个大于所有 ASCII 码值的质数 - 对一个大质数
m取模以防止数值溢出
例如字符串 "abac" 的哈希值为：
int('a') * B^3 + int('b') * B^2 + int('a') * B + int('c')
4.2 实现
我们使用两个数组：
prefix[i]：前i个字符组成的子串的哈希值pow[i]：B^i对m取模的结果
初始化函数如下：
algorithm ImprovedHashStructureInit(s, B, m):
n <- length(s)
Pre <- new array[n]
Pow <- new array[n]
Pre[0] <- int(s[0])
Pow[0] <- 1
for i <- 1 to n - 1:
Pre[i] <- (Pre[i - 1] * B + int(s[i])) % m
Pow[i] <- (Pow[i - 1] * B) % m
获取子串哈希值的函数如下：
algorithm getHash(L, R, m, Pre, Pow):
if L = 0:
return Pre[R]
return (Pre[R] - (Pre[L - 1] * Pow[R - L + 1]) % m + m) % m
预处理复杂度为 O(n)，哈希查询复杂度为 O(1)。
使用该哈希函数能显著降低冲突概率，从而提升 Rabin-Karp 的平均效率。
5. Rabin-Karp 的变体
5.1 非确定性版本
该版本使用多个哈希函数（不同 B 和 m）来进一步降低冲突概率：
- 如果多个哈希函数的值都相同，我们认为字符串匹配的可能性极高
- 可以省去字符逐个比较步骤，从而将复杂度优化为
O(n + k)
5.2 多个等长模式串
Rabin-Karp 可以扩展用于处理多个等长的模式串：
- 先对每个模式串计算哈希值并存入 Map
- 扫描文本时，检查当前子串的哈希值是否存在于 Map 中
确定性版本复杂度为 O(n + SumPatterns + SumMatches)，非确定性版本为 O(n + SumPatterns)。
6. 总结
本文介绍了字符串搜索问题及两种主要算法：
- 朴素算法简单但效率低，复杂度为
O(n * k) - Rabin-Karp 利用哈希函数优化搜索过程，期望复杂度可降至
O(n + k * t) - 更好的哈希函数能显著减少冲突，提升性能
- 可扩展用于多个模式串和非确定性场景
Rabin-Karp 是一个在实践中非常实用的字符串搜索算法，尤其适合处理大规模文本和多模式匹配场景。