字符串匹配之 Rabin-Karp算法（RK）

缘起

关于字符串匹配的算法，我们之前介绍了KMP、BM、扩展KMP（注意，扩展KMP和KMP本质上讲不是一个思路，其实扩展KMP不仅有着和KMP一样的性能，而且比KMP需要的数学推导更加简单）.

毫无例外的涉及失配情形下的跳转推导. 较为复杂, 本文介绍一种基于哈希的”暴力” 算法. 但是有着不错的性能和极为简单的实现, 就是著名的KR算法，由Karp和Rabin发明.

分析

其实KR算法审视两个字符串匹配的视角就是hash

两个字符串不匹配但是哈希值相等是小概率事件!!!

这句话就足以概括KR算法的核心思想了~

用T表示文本串, p表示模式串. n是T的长度，m是p的长度.

T[i,…,i+m-1]=p[0,…,m-1] 可以推出必要非充分条件是

hash(T[i,…,i-m+1])=hash(p[0,..,m-1])

所以我们在真正逐字节匹配字符串前，可以先计算一下他俩的哈希值，如果不相等，则根本没有逐字节比较的必要!

所以KR算法的核心是如何高效的维护并计算哈希值了.

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include "stdafx.h"
#include <iostream>
#include <cstring>
#define LOCAL
using namespace std;

const int MAX_T = 255, MAX_P = 20;

char T[MAX_T], p[MAX_P];

int n,m, hashp, hasht; // hashp是p的哈希值,hasht是文本串的m长度的子串的哈希值

void kr()
{
	for (int i = 0; i<m;i++)
	{
		hashp = (hashp<<1) + p[i];
		hasht = (hasht<<1) + T[i];
	} // 预处理得到p[0,..,m-1]的哈希值以及T[0,...,m-1]的哈希值, 其中这里的哈希函数选做 p[0]*2^(m-1)+...+p[m-1]
	for (int i =0 ;i<=n-m; i++) // 最后要考察 T[n-m,...,n-1] 与 p[0,..., m-1]的匹配
	{
		if (hashp==hasht && !memcmp(p, T+i, m)) printf("%d\n", i);  // 如果T[i,...,i+m-1]和p[0,..,m-1]匹配, 注意, && 是短路运算符——如果哈希值都不相等的话, 根本不会进行逐字节的比较，所以基本上是不会进来比较的.除非匹配
		hasht=((hasht-(T[i]<<(m-1)))<<1)+T[i+m]; // O(1)时间维护T的m长度的子串的哈希值是RK算法O(n+m)实现的关键
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%s%s", T, p);
	n = strlen(T), m = strlen(p);
	kr();
	return 0;
}
/*
测试数据
myGoogleyouGoogleLove Google
*/

可以感觉到, KR算法是一个极精妙的算法——简单，但是不失效率. 算法复杂度是O(N+M)

那为什么算法竞赛中用的少呢? 因为哈希值容易溢出啊~ 所以用的不多.