17

根据关于 Rabin-Karp 字符串匹配算法的维基百科条目，它可用于同时在字符串中查找几种不同的模式，同时仍保持线性复杂度。很明显，当所有模式的长度相同时，这很容易做到，但我仍然不明白如何在同时搜索不同长度的模式时保持 O(n) 复杂度。有人可以对此有所了解吗？

编辑（2011 年 12 月）：

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

4

2 回答 2

5

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

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

当然，我们必须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) 时间复杂度。

于 2009-08-23T09:40:51.960 回答
0

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

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

这是一个链接，其中对此进行了更详细的描述（例如，参见“是什么让 Rabin-Karp 快速？”部分）

于 2009-08-23T10:14:58.337 回答