使用 Rabin-Karp 算法在字符串中搜索多个模式

Question

根据Rabin-Karp字符串匹配算法的维基百科条目，它可以同时查找一个字符串中的多种不同模式，同时保持线性复杂度。显然，当所有模式具有相同长度时，这很容易实现，但我仍然不明白如何在搜索具有不同长度的模式时保持O(n)复杂度。能否有人解释一下？

编辑（2011年12月）：

维基百科文章已更新，不再声称以O(n)的复杂度匹配多个不同长度的模式。

- MAK

---

这并不是确切的答案，因为它只处理一次搜索一个字符串，而不是多个，但在http://www-igm.univ-mlv.fr/~lecroq/string/index.html下有一些可能有用的信息（在“Karp Rabin”标题下），可以帮助您。 - Jonathan Leffler

维基百科文章声称它可以在O(n)时间内找到多个模式。 - MAK

Answer 1

我不确定这是否是正确答案，但无论如何：

在构造哈希值时，我们可以检查字符串哈希集合中的匹配项。也就是说，当前哈希值。哈希函数/代码通常被实现为循环，在该循环内，我们可以插入快速查找。

当然，我们必须从字符串集合中选择 m 以获得最大的字符串长度。

更新：来自维基百科，

[...]
for i from 1 to n-m+1
         if hs ∈ hsubs
             if s[i..i+m-1] = a substring with hash hs
                 return i
         hs := hash(s[i+1..i+m]) // <---- calculating current hash
[...]

我们在m步内计算当前哈希值。每一步都有一个临时哈希值，我们可以在哈希集合中查找（复杂度为O(1)）。所有哈希值的大小都相同，即32位。

更新2：均摊（平均）O(n)时间复杂度？

上面我说过m必须具有最大字符串长度。事实证明，我们可以利用相反的情况。
通过哈希用于移位子字符串搜索和固定的m大小，我们可以实现O(n)的复杂度。

如果我们有可变长度的字符串，我们可以将m设置为最小字符串长度。此外，在哈希集合中，我们不是将哈希与整个字符串相关联，而是与其前m个字符相关联。
现在，在搜索文本时，我们检查当前哈希是否在哈希集合中，并检查相关的字符串是否匹配。

这种技术会增加误报率，但平均而言它具有O(n)的时间复杂度。

- Nick Dandoulakis

---

谢谢您的解释。但这正是我困惑的根源。 如果我们在m步中计算当前哈希值，那么我们的总体复杂度就不再是线性的了。它变成了O(n*m)（n是字符串的长度，m是最长模式的长度）。 - MAK

我开始觉得维基百科上的记录可能是错误的。它声称复杂度应为O（n + k）。再次感谢。 - MAK

@MAK，看更新2。如果我想到更好的解决方案，我会发布新的更新。 - Nick Dandoulakis

我知道这样的情况。这种数据展示了算法最糟糕的部分。可能有一种方法可以最小化误报，但我还没有想出来。 - Nick Dandoulakis

请注意，即使是在最坏的情况下，快速排序也需要进行Θ(n2)次比较 ;)（借口，借口，借口） - Nick Dandoulakis

Answer 2

这是因为子字符串的哈希值在数学上是相关的。计算从字符串S的第j个位置开始的字符的哈希值H(S,j)需要O(m)时间，其中m是字符串的长度。但是一旦你有了它，计算H(S, j+1)可以在常数时间内完成，因为H(S, j+1)可以表示为H(S, j)的函数。

O(m) + O(1) => O(m)，即线性时间。

这里是一个链接，其中更详细地描述了这一点（例如，请参见“什么使Rabin-Karp快？”部分）

- ire_and_curses

---

我明白为什么Rabin-Karp算法很快。我以前用过它来在字符串中查找单个模式。我正在尝试弄清楚如何使用它同时在一个字符串中以O(n)的时间复杂度查找多个模式（而不是逐个搜索k个模式的O(n*k)时间复杂度）。 - MAK

@MAK：抱歉，我误解了你的问题。那不是在维基百科文章底部的答案吗？“相比之下，上面的Rabin-Karp变体可以在期望的O(n+k)时间内找到所有k个模式，因为哈希表检查子字符串哈希是否等于任何模式哈希的时间复杂度为O(1)。”创建哈希的时间复杂度为O(k)。在哈希表中查找匹配项是一个O(1)操作。如果有任何匹配项，你就赢了。 - ire_and_curses