RabinKarp RabinKarp算法

PreviousKnuthMorrisPratt KMP匹配算法 NextBoyerMoore BoyerMoore算法

Last updated 6 years ago

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]) % prime

Rabin-Karp

Rabin Fingerprint

源码

测试

PreviousKnuthMorrisPratt KMP匹配算法 NextBoyerMoore BoyerMoore算法

Last updated 6 years ago

问题

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

解法

hash(0, i+1) = hash(0, i) \cdot base + text[i+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]) % prime

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$ 在文本中出现的次数。