RabinKarp RabinKarp算法

问题

在文本$text$中查找模式$pattern$出现的所有位置（$text$长度为$n$，$pattern$长度为$m$，$n, m$都是正整数且$n \gt m$）。

解法

从位置$i, j$开始的匹配，每次成功的匹配都需要时间复杂度为$O(m)$的遍历，才能确定$text[i \dots i+m-1] = pattern[0 \dots m-1] = pattern$是否成立。如果用$hash(i, i+m-1)$来表示字符串$text[i \dots i+m-1]$的哈希值，$hash(pattern)$表示字符串$pattern$的哈希值，则比较$hash(i, i+m-1) = hash(pattern)$是否成功的时间复杂度为$O(1)$。显然当$hash(i, i+m-1) \ne hash(pattern)$时必然有$text[i \dots i+m-1] \ne pattern$。反之若哈希值相同，再用简单匹配来确定字符串$text[i \dots i+m-1] = pattern$确实为真，这样即可找出所有成功匹配。

我们通过Rabin Fingerprint算法计算字符串的哈希值，ASCII码中每个字符对应的数字值范围在$[0 - 127]$之间，设每读入新的字符时旧的哈希值的扩大倍数为$base = 128$（这个$base$是字符表大小的范围）。则有：

$$hash(0, i+1) = hash(0, i) \cdot base + text[i+1]$$

实际我们想计算的是$hash(text[i \dots i+m-1])$，当$i$右移一位时，不仅要考虑右边界新加入的字符，还需要考虑左边界离开的字符。一个字符从最右边界一直移动到最左边界，其值乘以$base$共$m-1$次。因此哈希值要减去$base^{m-1} \cdot text[i]$。特别注意$pattern$长度为$1$时$base^{m-1} = 1$：

$$hash(i+1, i+m) = hash(i, i+m-1) \cdot base - base^{m-1} \cdot text[i] + text[i+1]$$

由于数字太大时计算会溢出，用一个较大的素数来对结果取模$prime = 16777619$，最终得到哈希函数：

$$hash(i+1, i+m]) = (hash(i, i+m-1) \cdot base - base^{m-1} \cdot text[i] + text[i+1])$$

Rabin Fingerprint算法可以连续的处理字符串，在时间复杂度为$O(n)$内求出所有字符串$text[i \dots i+m-1]$的哈希值（其中$0 \ge i \ge n-m+1$）。Rabin-Karp算法的时间复杂度为$O(n + z \cdot m)$，其中$z$是模式$pattern$在文本中出现的次数。

Rabin-Karp

• http://www.cs.cmu.edu/afs/cs/academic/class/15451-f14/www/lectures/lec6/karp-rabin-09-15-14.pdf

• https://www.geeksforgeeks.org/rabin-karp-algorithm-for-pattern-searching/

Rabin Fingerprint

• http://www.xmailserver.org/rabin.pdf

• https://pdos.csail.mit.edu/papers/lbfs:sosp01/lbfs.pdf

源码

RabinKarp.h

RabinKarp.cpp

测试

RabinKarpTest.cpp