Rabin-Karp 算法简介

Created: November-22, 2018

Rabin-Karp 算法是由 Richard M. Karp和 Michael O. Rabin创建的字符串搜索算法，它使用散列来查找文本中的一组模式字符串中的任何一个。

字符串的子字符串是另一个出现的字符串。例如， ver 是 stackoverflow 的子字符串。不要与子序列混淆，因为 cover 是同一个字符串的子序列。换句话说，字符串中连续字母的任何子集都是给定字符串的子字符串。

在 Rabin-Karp 算法中，我们将生成我们正在寻找的模式的哈希，并检查我们的文本的滚动哈希是否与模式匹配。如果它不匹配，我们可以保证的是，模式不存在的文本。但是，如果匹配，则模式可以出现在文本中。我们来看一个例子：

假设我们有一个文本： yeminsajid ，我们想知道文本中是否存在模式 nsa 。要计算散列和滚动散列，我们需要使用素数。这可以是任何素数。让我们在这个例子中使用 prime = 11 。我们将使用以下公式确定哈希值：

(1st letter) X (prime) + (2nd letter) X (prime)¹ + (3rd letter) X (prime)² X + ......

我们将表示：

a -> 1    g -> 7    m -> 13   s -> 19   y -> 25
b -> 2    h -> 8    n -> 14   t -> 20   z -> 26
c -> 3    i -> 9    o -> 15   u -> 21
d -> 4    j -> 10   p -> 16   v -> 22
e -> 5    k -> 11   q -> 17   w -> 23
f -> 6    l -> 12   r -> 18   x -> 24

nsa 的哈希值为：

 14 X 11⁰ + 19 X 11¹ + 1 X 11² = 344

现在我们找到文本的滚动哈希值。如果滚动哈希与模式的哈希值匹配，我们将检查字符串是否匹配。因为我们的模式有 3 个字母，我们将采取 1 日 3 封 YEM 从我们的文本，并计算哈希值。我们得到：

25 X 11⁰ + 5 X 11¹ + 13 X 11² = 1653

此值与我们的模式的哈希值不匹配。所以字符串在这里不存在。现在我们需要考虑下一步。计算下一个字符串 emi 的哈希值。我们可以使用我们的公式计算出来。但这将是相当微不足道的，并且会花费更多。相反，我们使用另一种技术。

我们从当前哈希值中减去 Previous String 的第一个字母的值。在这种情况下， y 。我们得到了，1653 - 25 = 1628。
我们将差异除以我们的素数，这个例子是 11 。我们得到了，1628 / 11 = 148。
我们加上新的字母 X（素数）ᵐ-1 ，其中 m 是模式的长度，商是 i = 9 。我们得到了，148 + 9 X 11² = 1237。

新的哈希值不等于我们的模式哈希值。继续前进，为 ñ 我们得到：

Previous String: emi
First Letter of Previous String: e(5)
New Letter: n(14)
New String: "min"
1237 - 5 = 1232
1232 / 11 = 112
112 + 14 X 11² = 1806

它不匹配。在那之后，对于 s ，我们得到：

Previous String: min
First Letter of Previous String: m(13)
New Letter: s(19)
New String: "ins"
1806 - 13 = 1793
1793 / 11 = 163
163 + 19 X 11² = 2462

它不匹配。接下来，对于 a ，我们得到：

Previous String: ins
First Letter of Previous String: i(9)
New Letter: a(1)
New String: "nsa"
2462 - 9 = 2453
2453 / 11 = 223
223 + 1 X 11² = 344

这是一个匹配！现在我们将模式与当前字符串进行比较。由于两个字符串都匹配，因此子字符串存在于此字符串中。然后我们返回子字符串的起始位置。

伪代码将是：

哈希计算：

Procedure Calculate-Hash(String, Prime, x):
hash := 0                                  // Here x denotes the length to be considered
for m from 1 to x                          // to find the hash value
    hash := hash + (Value of String[m])ᵐ⁻¹
end for
Return hash

哈希重新计算：

Procedure Recalculate-Hash(String, Curr, Prime, Hash):
Hash := Hash - Value of String[Curr]  //here Curr denotes First Letter of Previous String
Hash := Hash / Prime
m := String.length
New := Curr + m - 1
Hash := Hash + (Value of String[New])ᵐ⁻¹
Return Hash

字符串匹配：

Procedure String-Match(Text, Pattern, m):
for i from m to Pattern-length + m - 1
    if Text[i] is not equal to Pattern[i]
        Return false
    end if
end for
Return true

拉宾，卡普：

Procedure Rabin-Karp(Text, Pattern, Prime):
m := Pattern.Length
HashValue := Calculate-Hash(Pattern, Prime, m)
CurrValue := Calculate-Hash(Pattern, Prime, m)
for i from 1 to Text.length - m
    if HashValue == CurrValue and String-Match(Text, Pattern, i) is true
        Return i
    end if
    CurrValue := Recalculate-Hash(String, i+1, Prime, CurrValue)
end for
Return -1

如果算法找不到任何匹配，则只返回 -1 。

该算法用于检测抄袭。在给定源材料的情况下，该算法可以快速在纸张中搜索来自源材料的句子实例，忽略诸如大小写和标点符号之类的细节。由于所搜索的字符串丰富，单字符串搜索算法在这里是不切实际的。同样， Knuth-Morris-Pratt 算法或 Boyer-Moore 字符串搜索算法是比 Rabin-Karp 更快的单模式字符串搜索算法。但是，它是多模式搜索的首选算法。如果我们想在文本中找到任何大数，比如 k，固定长度模式，我们可以创建一个简单的 Rabin-Karp 算法变体。

对于组合长度为 m 的长度为 n 和 p 的模式的文本，其平均和最佳情况运行时间在空间 O(p) 中为 O（n + m ），但其最坏情况时间为 O(nm) 。 **** **** **** ****