Rabin Karp 算法

基本概念

Rabin Karp（RK）算法：由 Michael Oser Rabin 与 Richard Manning Karp 于 1987 年提出，是一种利用哈希快速筛查匹配起点的单模式串匹配算法。

  • Rabin Karp 算法核心思想：给定文本串 T 与模式串 p，先计算 p 的哈希值，再对T的所有长度为 m=∣p∣的子串高效计算哈希。借助「滚动哈希」在 O(1)时间更新相邻子串的哈希，用哈希相等作为快速筛选，仅在相等时再逐字符比对以排除哈希冲突。

算法步骤

  1. 设n=∣T∣、m=∣p∣
  2. 计算模式串哈希H(p)
  3. 计算文本首个长度为m的字串T[0,m−1]​T[0,m−1]​的哈希 H(T[0,m−1])H(T[0,m−1]),并用滚动哈希依次得到其余n-m个相邻字串的哈希
  4. 逐一比较H(T[i,i+m−1])H(T_{[i,i+m-1]})与H(p):
    • 如果不相等，跳过
    • 如果相等，逐字符核验：完全相同则返回起点i，否则继续
  5. 全部位置检查后仍未匹配，返回-1

内部实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# T: 文本串，p: 模式串，d: 字符集大小（基数），q: 模数（质数）
def rabinKarp(T:stt,p:str, d:int, q:int )->int:
	n,m=len(T),len(p)
	if m == 0:
		return 0
	if n< m:
		return -1
	hash_p,hash_t=0,0
	for i in range(m):
		hash_p=(hash_P*d+ord(p[i]))%q
		hash_t=(hash_t*d+ord(T[i]))%q
	power=pow(d,m-1,q)
	for i in range(n-m+1):
		if  hash_p == hash_t:
			match = True
			for j in range(m):
				if T[i+j]!=p[j]:
					match=False
					break
			if match:
				return i
		if i <n-m:
			hash_t = (hash_t-power*ord(p[i]))%q
			hash_t=(hash_t*d+rod(T[i+m]))%q
	return -1

复杂度分析：

指标 复杂度 说明
最好时间复杂度 O(n−m+1) 无哈希冲突时，仅需 n−m+1 次哈希对比，均为 O(1)，无需逐字符校验
最坏时间复杂度 O(m(n−m+1))≈O(nm) 每次哈希均冲突，需 n−m+1 次逐字符全量比对，每次 O(m)
平均时间复杂度 O(n−m+1) 期望哈希冲突极少，绝大多数位置仅哈希对比，均摊 O(1)
空间复杂度 O(1) 仅需常数变量存储哈希值与辅助参数

说明：与 BF 相比，RK 通过哈希筛选把大多数不匹配位置在 O(1)内排除；但哈希冲突会触发逐字符校验，致使最坏复杂度退化。
Rabin-Karp（RK）算法通过将模式串和文本子串转化为哈希值，利用滚动哈希快速筛查匹配位置，大幅减少无效字符比较。其平均时间复杂度远优于朴素算法，适合大文本和多模式串场景，但哈希冲突时需回退逐字符比对，最坏情况下复杂度与朴素法相同。合理选择哈希参数可有效降低冲突概率，是一种高效且易于扩展的字符串匹配算法。

  • 优点：
    • 滚动哈希使子串哈希更新为 O(1)，平均性能优于 BF；
    • 易于扩展到多模式串场景（统一维护多哈希）。
  • 缺点：
    • 存在哈希冲突，最坏复杂度可退化至 O(nm)；
    • 需合理选择基数 d 与大质数模 q，以降低冲突概率。

应用场景