Rabin-Karp字符串匹配算法
滚动哈希的高效字符串匹配
一、算法概述
Rabin-Karp算法是由 Richard M. Karp 和 Michael O. Rabin 于 1987 年提出的字符串匹配算法。该算法利用哈希函数将字符串映射为整数值，通过比较哈希值来判断子串是否与模式串匹配，从而避免了逐字符比较的开销。
与传统的暴力匹配算法不同，Rabin-Karp的核心创新在于滚动哈希（Rolling Hash）技术：当窗口在文本中滑动时，可以在 O(1) 时间内计算出新窗口的哈希值，而不需要重新计算整个子串。这一特性使得 Rabin-Karp 在多模式匹配场景中展现出独特的优势。
算法核心特性
- 哈希映射： 将字符串转换为数值哈希，比较哈希而非比较字符
- 滚动哈希： 利用数学递推关系，O(1) 时间完成滑动窗口哈希更新
- 哈希值比较： 仅当哈希值相等时才进行逐字符验证，避免误匹配
二、核心思想
2.1 哈希映射
Rabin-Karp算法的第一个关键思想是将字符串看作一个基于某个基数的数字。例如，对于只包含小写字母的字符串，我们可以将每个字符映射为一个数字（a=1, b=2, ..., z=26），然后将整个字符串视为一个 base=26 的数字。
给定一个长度为 m 的模式串 P，我们计算其哈希值 hash(P)。当在文本串 T 中滑动窗口时，对每个长度为 m 的子串 T[i..i+m-1]，计算其哈希值 hash(T[i..i+m-1])。如果 hash(P) == hash(T[i..i+m-1])，则说明模式串可能与当前子串匹配，此时再进行逐字符验证。
多项式哈希公式
对于字符串 s = s₀s₁...s_{m-1}，其多项式哈希值定义为：
hash(s) = (s₀ × d^{m-1} + s₁ × d^{m-2} + ... + s_{m-1} × d⁰) mod q
其中 d 为基数（通常选择一个大于字符集大小的素数），q 为模数（一个大素数），s_i 为字符对应的整数值。
2.2 滚动哈希
滚动哈希是 Rabin-Karp 算法的灵魂。当窗口从位置 i 滑动到位置 i+1 时，我们不需要重新计算整个子串的哈希值，而是可以利用上一个窗口的哈希值通过常数时间的运算得到新窗口的哈希值。
具体推导过程如下：设当前窗口为 T[i..i+m-1]，其哈希值为 hash_i：
hash_i = (T[i] × d^{m-1} + T[i+1] × d^{m-2} + ... + T[i+m-1] × d⁰) mod q
滑动一个字符后，新窗口为 T[i+1..i+m]，其哈希值为：
hash_{i+1} = ((hash_i - T[i] × d^{m-1}) × d + T[i+m]) mod q
如果 hash_i - T[i] × d^{m-1} 为负，则先加 q 再运算。
这个递推公式意味着每次窗口滑动只需要 O(1) 时间即可完成哈希值更新，而不是 O(m) 时间。
三、滚动哈希设计
3.1 基数选择
基数的选择直接影响哈希的分布质量。通常的选值原则：
- 大于字符集大小： 确保不同字符序列能够映射到不同的数值范围。例如 ASCII 字符集选择 256 或 257，小写字母选择 26 或 27
- 素数最佳： 选择素数作为基数可以减少哈希冲突的概率
- 常见选择： 对于 ASCII 字符串，常用 131、137、256 等值
3.2 模数选择
模数的作用是将哈希值限制在一个可控范围内，同时减少冲突。模数选择的原则：
- 选用大素数： 如 10⁹+7、10⁹+9、2⁶⁴（利用自然溢出）等
- 避免 2 的幂： 模 2ⁿ 时哈希值的低位分布不均匀，容易产生碰撞
- 常见模数： 1,000,000,007、1,000,000,009、9,982,445,353
3.3 防溢出策略
在计算哈希值时，中间结果可能非常大（d^{m-1} 可能远超整数范围）。常用的防溢出策略有三种：
策略一：取模运算
所有乘法、加法运算后立即对模数 q 取模，确保哈希值始终在 [0, q-1] 范围内。这是最常用的方法，适用于所有编程语言。
策略二：无符号整数自然溢出
在 C/C++/Java 等语言中，使用无符号 64 位整数（unsigned long long），让乘法运算自然溢出，相当于对 2⁶⁴ 自动取模。这种方法速度极快，但需要注意模数不是素数，冲突概率略高。
策略三：双哈希
同时使用两个不同的模数（如 10⁹+7 和 10⁹+9）计算哈希值，只有当两个哈希值都相等时才认为匹配。这是处理哈希碰撞最可靠的方法之一。
四、匹配过程
Rabin-Karp 算法的完整匹配过程可以概括为以下几个步骤：
- 计算模式串哈希： 使用多项式哈希公式计算模式串 P 的哈希值 hash(P)
- 预计算最高位权值： 计算 d^{m-1} mod q，用于滚动哈希的移出操作
- 计算第一个窗口哈希： 计算文本串中第一个长度为 m 的子串 T[0..m-1] 的哈希值
- 滚动比较： 对文本串中的每个位置 i（从 0 到 n-m），比较当前窗口哈希值与 hash(P)
- 哈希碰撞处理： 当哈希值相等时，进行逐字符验证确认是否真正匹配
- 窗口滑动： 使用滚动哈希公式计算下一个窗口的哈希值，重复步骤 4-5
4.1 完整匹配演示
假设文本串 T = "abcabaabcabac"，模式串 P = "abaa"，基数 d = 256，模数 q = 101：
步骤详解：
1. 计算模式串 "abaa" 的哈希值：
hash(P) = ('a'*256³ + 'b'*256² + 'a'*256¹ + 'a'*256⁰) mod 101
= (97*256³ + 98*256² + 97*256¹ + 97*256⁰) mod 101
2. 计算文本串中每个窗口的哈希值（滚动更新）：
窗口1 "abca": hash = ...
窗口2 "bcab": hash = ((hash1 - 'a'*256³) * 256 + 'b') mod 101
窗口3 "caba": hash = ((hash2 - 'b'*256³) * 256 + 'c') mod 101
...
3. 当 hash(窗口) == hash(P) 时，逐字符验证是否真匹配。
五、哈希碰撞问题
哈希碰撞是指两个不同的字符串具有相同的哈希值。在 Rabin-Karp 算法中，哈希碰撞会导致误匹配，需要进行额外的逐字符验证，从而影响算法性能。
5.1 碰撞原因
- 模数空间有限： 哈希值取值范围为 [0, q-1]，而可能的字符串数量远大于 q
- 基数选择不当： 基数过小或与字符集大小不互质时，容易产生系统性的碰撞
- 输入分布特殊： 某些特定模式的输入会导致大量碰撞
5.2 解决方案
方案一：双哈希（Double Hashing）
使用两个不同的模数 q₁ 和 q₂ 同时计算哈希值。只有当 hash₁(P) == hash₁(T[i]) 且 hash₂(P) == hash₂(T[i]) 时才判定为可能匹配。双哈希将碰撞概率从 1/q 降低到 1/(q₁·q₂)，几乎可以忽略不计。
// 双哈希实现
int mod1 = 1000000007;
int mod2 = 1000000009;
long long hash1_p = computeHash(P, base, mod1);
long long hash2_p = computeHash(P, base, mod2);
long long hash1_t = computeHash(T, 0, m, base, mod1);
long long hash2_t = computeHash(T, 0, m, base, mod2);
if (hash1_t == hash1_p && hash2_t == hash2_p) {
// 极大概率是真匹配，仍需逐字符验证
}
方案二：大模数 + 自然溢出
使用 64 位无符号整数的自然溢出（等价于模 2⁶⁴）作为模数。2⁶⁴ 的取值空间极大，碰撞概率很低。但需要注意模数不是素数，理论上碰撞概率比素数模数略高。
方案三：确定性处理
在哈希值匹配后进行逐字符验证，确保匹配的准确性。这是 Rabin-Karp 算法中最基本的碰撞处理方式，虽然最坏情况下会退化为 O(nm)，但在平均情况下效率很高。
六、Rabin-Karp vs KMP 对比
KMP（Knuth-Morris-Pratt）算法和 Rabin-Karp 是两种最经典的字符串匹配算法，它们在设计理念和性能特征上有着显著的差异：
| 对比维度 |
Rabin-Karp 算法 |
KMP 算法 |
| 核心思想 |
哈希比较 + 滚动哈希 |
前缀函数 + 状态转移 |
| 预处理时间 |
O(m) |
O(m) |
| 匹配时间（平均） |
O(n+m) |
O(n+m) |
| 匹配时间（最坏） |
O(nm) |
O(n+m) |
| 空间复杂度 |
O(1) |
O(m) |
| 多模式匹配 |
天然支持，O(n + k·m) |
需改造为 AC 自动机 |
| 随机访问 |
需要随机访问文本 |
顺序扫描即可 |
| 数值敏感度 |
对哈希碰撞敏感 |
无碰撞问题 |
| 适用场景 |
多模式匹配、近似匹配 |
单模式精确匹配 |
选型建议
- 单模式匹配、最坏性能敏感： 选择 KMP，因为它提供严格 O(n+m) 的最坏时间复杂度保证
- 多模式匹配、平均性能优先： 选择 Rabin-Karp，特别是模式串数量多时优势明显
- 需要同时检测多个模式： Rabin-Karp 是最自然的选择，无需额外数据结构
- 输入规模极大且不可预测： 考虑结合使用，或在 Rabin-Karp 基础上加双哈希保证
七、多模式匹配优势
Rabin-Karp 算法最独特的优势在于其天然支持多模式匹配。当我们需要在一个文本串中同时查找多个模式串时，Rabin-Karp 的滚动哈希机制可以发挥出极大的效率。
7.1 多模式匹配原理
假设有 k 个模式串 P₁, P₂, ..., Pk，长度分别为 m₁, m₂, ..., mk。在多模式匹配场景中：
- 预处理阶段： 计算所有模式串的哈希值，存储在一个哈希集合中
- 匹配阶段： 对于文本串中的每个窗口，只需计算一次滚动哈希值，然后检查该哈希值是否存在于模式串哈希集合中
- 效率对比： 暴力方法需要对每个模式串分别进行一次完整的匹配过程，时间复杂度 O(k·(n+m))。而 Rabin-Karp 的多模式匹配仅需 O(n + k·m + n·m_avg)（在碰撞较少的情况下）
// 多模式匹配 Rabin-Karp 伪代码
function multiPatternRabinKarp(text, patterns):
n = text.length
// 按长度分组（不同长度的模式串需要不同的滚动窗口）
groups = groupByLength(patterns)
for each (length, patternList) in groups:
m = length
patternHashes = new Set()
for pattern in patternList:
patternHashes.add(computeHash(pattern))
windowHash = computeHash(text[0..m-1])
for i in 0 to n-m:
if windowHash in patternHashes:
// 验证该位置匹配的具体模式串
verifyMatch(text, i, patternList)
if i < n-m:
windowHash = rollHash(windowHash, text[i], text[i+m], m)
7.2 实际应用场景
- 入侵检测系统： 同时检测数据包中是否包含多个攻击特征码
- 敏感词过滤： 在文本中同时查找多个敏感词汇
- 基因序列分析： 同时在 DNA 序列中查找多个基因标记
- 抄袭检测： 检测文档中是否包含多个来源的文本片段
八、时间复杂度分析
平均情况：O(n+m)
在平均情况下，哈希值在 [0, q-1] 范围内均匀分布，哈希碰撞的概率约为 1/q。当 q 足够大（如 10⁹+7）时，碰撞极少发生，逐字符验证的次数可以忽略不计。因此：
- 预处理： O(m) 计算模式串哈希
- 滚动过程： O(n) 每个窗口 O(1) 更新哈希
- 验证过程： O(1) 平均（碰撞极少）
- 总计： O(n+m)
最坏情况：O(nm)
在最坏情况下，每个窗口的哈希值都与模式串的哈希值相等（例如，文本和模式都是同一个字符重复组成，如 T="aaaa...a", P="aaa"），此时每个窗口都需要进行 O(m) 的逐字符验证：
- 验证次数： n-m+1 ≈ n 次
- 每次验证： O(m)
- 总计： O(nm)
这就是为什么 Rabin-Karp 的最坏时间复杂度不如 KMP 稳定的原因。但在实际应用中（尤其是使用双哈希或大模数时），最坏情况几乎不会出现。
时间复杂度总结：
┌─────────────────────┬─────────────┬──────────────┐
│ 阶段 │ 平均情况 │ 最坏情况 │
├─────────────────────┼─────────────┼──────────────┤
│ 预处理（模式哈希） │ O(m) │ O(m) │
│ 滚动计算窗口哈希 │ O(n) │ O(n) │
│ 逐字符验证 │ O(1)* │ O(nm) │
├─────────────────────┼─────────────┼──────────────┤
│ 总计 │ O(n+m) │ O(nm) │
└─────────────────────┴─────────────┴──────────────┘
*平均情况下碰撞极少，验证视为常数时间
九、完整代码实现
9.1 Java 实现
public class RabinKarp {
private final int d;
private final int q;
private int patternHash;
private int h;
private String pattern;
private int m;
public RabinKarp(String pattern) {
this.pattern = pattern;
this.d = 256;
this.q = 1000000007;
this.m = pattern.length();
h = 1;
for (int i = 0; i < m - 1; i++) {
h = (h * d) % q;
}
patternHash = 0;
for (int i = 0; i < m; i++) {
patternHash = (d * patternHash + pattern.charAt(i)) % q;
}
}
public int search(String text) {
int n = text.length();
if (n < m) return -1;
int textHash = 0;
for (int i = 0; i < m; i++) {
textHash = (d * textHash + text.charAt(i)) % q;
}
for (int i = 0; i <= n - m; i++) {
if (textHash == patternHash) {
boolean match = true;
for (int j = 0; j < m; j++) {
if (text.charAt(i + j) != pattern.charAt(j)) {
match = false;
break;
}
}
if (match) {
return i;
}
}
if (i < n - m) {
textHash = (d * (textHash - text.charAt(i) * h) + text.charAt(i + m)) % q;
if (textHash < 0) {
textHash += q;
}
}
}
return -1;
}
}
9.2 Python 实现
class RabinKarp:
"""
Rabin-Karp 字符串匹配算法实现
使用滚动哈希进行高效字符串匹配
"""
def __init__(self, pattern: str, d: int = 256, q: int = 1000000007):
self.pattern = pattern
self.d = d
self.q = q
self.m = len(pattern)
self.pattern_hash = self._compute_hash(pattern, 0, self.m)
self.h = pow(d, self.m - 1, q) if self.m > 0 else 1
def _compute_hash(self, s: str, start: int, length: int) -> int:
"""计算字符串 s[start:start+length] 的哈希值"""
h_val = 0
for i in range(start, start + length):
h_val = (self.d * h_val + ord(s[i])) % self.q
return h_val
def search(self, text: str) -> int:
"""
在文本串 text 中搜索模式串
返回第一个匹配位置的索引，未找到则返回 -1
"""
n = len(text)
if n < self.m:
return -1
text_hash = self._compute_hash(text, 0, self.m)
for i in range(n - self.m + 1):
if text_hash == self.pattern_hash:
if text[i:i + self.m] == self.pattern:
return i
if i < n - self.m:
text_hash = (self.d * (text_hash - ord(text[i]) * self.h)
+ ord(text[i + self.m])) % self.q
return -1
def search_all(self, text: str) -> list:
"""返回所有匹配位置的列表"""
positions = []
n = len(text)
if n < self.m:
return positions
text_hash = self._compute_hash(text, 0, self.m)
for i in range(n - self.m + 1):
if text_hash == self.pattern_hash:
if text[i:i + self.m] == self.pattern:
positions.append(i)
if i < n - self.m:
text_hash = (self.d * (text_hash - ord(text[i]) * self.h)
+ ord(text[i + self.m])) % self.q
return positions
9.3 C++ 实现（带双哈希）
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
struct DualHash {
static const int MOD1 = 1000000007;
static const int MOD2 = 1000000009;
static const int BASE = 131;
ll h1, h2;
DualHash() : h1(0), h2(0) {}
DualHash(ll h1, ll h2) : h1(h1), h2(h2) {}
bool operator==(const DualHash& other) const {
return h1 == other.h1 && h2 == other.h2;
}
};
class RabinKarpDouble {
private:
string pattern;
DualHash patternHash;
ll pow1, pow2;
public:
RabinKarpDouble(const string& p) : pattern(p) {
int m = p.size();
if (m == 0) return;
ll h1 = 0, h2 = 0;
for (char c : p) {
h1 = (h1 * DualHash::BASE + c) % DualHash::MOD1;
h2 = (h2 * DualHash::BASE + c) % DualHash::MOD2;
}
patternHash = DualHash(h1, h2);
pow1 = 1; pow2 = 1;
for (int i = 0; i < m - 1; i++) {
pow1 = (pow1 * DualHash::BASE) % DualHash::MOD1;
pow2 = (pow2 * DualHash::BASE) % DualHash::MOD2;
}
}
vector<int> search(const string& text) {
vector<int> result;
int n = text.size(), m = pattern.size();
if (n < m || m == 0) return result;
ll h1 = 0, h2 = 0;
for (int i = 0; i < m; i++) {
h1 = (h1 * DualHash::BASE + text[i]) % DualHash::MOD1;
h2 = (h2 * DualHash::BASE + text[i]) % DualHash::MOD2;
}
for (int i = 0; i <= n - m; i++) {
if (h1 == patternHash.h1 && h2 == patternHash.h2) {
bool match = true;
for (int j = 0; j < m; j++) {
if (text[i + j] != pattern[j]) {
match = false;
break;
}
}
if (match) result.push_back(i);
}
if (i < n - m) {
h1 = ((h1 - text[i] * pow1) * DualHash::BASE + text[i + m]) % DualHash::MOD1;
h2 = ((h2 - text[i] * pow2) * DualHash::BASE + text[i + m]) % DualHash::MOD2;
if (h1 < 0) h1 += DualHash::MOD1;
if (h2 < 0) h2 += DualHash::MOD2;
}
}
return result;
}
};
十、算法优化与变种
10.1 性能优化技巧
- 预计算所有幂次： 将 d⁰, d¹, ..., d^{m-1} mod q 预先计算并存储，避免重复计算
- 使用 64 位无符号整数： 利用自然溢出避免取模运算的开销，在 C/C++ 中可显著提升速度
- 按模式长度分组： 多模式匹配时，将相同长度的模式串分组处理，避免重复的窗口扫描
- 提前终止： 当只需要查找第一个匹配时，找到后立即返回
10.2 常见变种
变种一：基于 Zobrist Hashing 的 Rabin-Karp
使用 Zobrist 哈希替代多项式哈希。Zobrist 哈希为每个字符在每种位置上分配一个随机数，哈希值为这些随机数的 XOR 和。滚动时只需 XOR 移除移入的字符对应随机数，无需乘法运算，在某些场景下性能更优。
变种二：二维 Rabin-Karp
将 Rabin-Karp 扩展到二维矩阵匹配。先对每行计算一维滚动哈希，再对列方向计算二次滚动哈希，可以在 O(n²) 时间内完成二维模式匹配，用于图像识别等领域。
变种三：近似匹配 Rabin-Karp
通过调整哈希比较策略，允许一定程度的字符差异（如 k 个字符不同），用于拼写检查、模糊搜索等场景。
十一、实际应用场景
- 文本编辑器中的查找功能： 在大型文件中快速搜索关键词
- 入侵检测系统（IDS）： 在网络数据包中同时检测多个攻击特征码，Rabin-Karp 的多模式匹配能力使其成为 Snort 等系统的核心算法
- 生物信息学： 在 DNA 序列分析中查找特定基因序列片段
- 剽窃检测： 将文档分割为多个指纹片段，通过哈希匹配检测相似内容
- 版本控制系统： git 等系统使用类似滚动哈希的思想检测文件中的重复内容块
- 搜索引擎： 在抓取的网页内容中快速定位查询关键词
十二、核心要点总结
- 核心创新： Rabin-Karp 将字符串比较转化为哈希值比较，利用滚动哈希实现 O(1) 时间窗口滑动
- 平均性能优异： 在合理参数下达到 O(n+m) 的平均时间复杂度，与 KMP 相当
- 多模式匹配王者： Rabin-Karp 天然支持同时匹配多个模式串，这是它优于 KMP 等算法的最大优势
- 滚动哈希关键三要素： 基数 d（大于字符集大小的素数）、模数 q（大素数）、递推公式 hash_{i+1} = ((hash_i - T[i] × d^{m-1}) × d + T[i+m]) mod q
- 哈希碰撞不可忽视： 通过双哈希或大模数 + 逐字符验证来处理碰撞问题
- 最坏情况： 在大量哈希碰撞时退化为 O(nm)，但通过双哈希可有效避免
- 适用场景： 特别适合多模式匹配和需要同时检测多个关键词的场景
十三、进一步思考
Rabin-Karp 算法的设计思想体现了算法设计中"化繁为简"的哲学：将复杂的字符串比较问题转化为简单的数值比较问题。这种"哈希化"的思路在计算机科学中有广泛应用。
扩展应用与思考
- 哈希思想的泛化： 任何支持哈希和滚动更新的数据结构都可以适配 Rabin-Karp 的思想，不仅仅局限于字符串
- 与 AC 自动机的关系： 在极端多模式（上万模式串）场景下，AC 自动机（Aho-Corasick）的 O(n) 确定性时间复杂度可能更优
- 滚动的本质： 滑动窗口 + 增量更新的思想不仅在字符串匹配中有用，在数据流分析、实时信号处理等领域都有应用
- 实际工程选择： 字符串匹配算法的选择需要综合考虑模式数量、文本规模、最坏性能要求等，没有绝对的最优算法
LeetCode 经典题目
- 28. 实现 strStr() - 基础字符串匹配，可用 Rabin-Karp 实现
- 187. 重复的DNA序列 - 使用滚动哈希查找长度为 10 的重复子串
- 1044. 最长重复子串 - 二分查找 + 滚动哈希的经典组合
- 214. 最短回文串 - 利用滚动哈希快速判断回文