使用 Rabin-Karp 搜索字符串中的多个模式-解网

问：

根据 Rabin-Karp 字符串匹配算法的维基百科条目，它可以用来同时在字符串中寻找几种不同的模式，同时仍然保持线性复杂度。很明显，当所有模式的长度相同时，这很容易做到，但我仍然不明白在同时搜索具有不同长度的模式时，我们如何保持 O（n）复杂性。有人可以对此进行一些说明吗？

编辑（2011 年 12 月）：

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

算法哈希语言无关字符串匹配 Rabin-Karp

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

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

当然，我们必须从字符串集中选择具有最大字符串长度。

更新：来自维基百科，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
[...]

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

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

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

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

这种技术会增加误报，但平均而言，它具有 O（n）时间复杂度。mmm

@MAK，如果所有字符串都是大小，并且我们按照使用哈希进行转移子字符串搜索一节中所述计算哈希值，则 O（n）是可行的。但是对于可变长度的字符串，IMO，O（nm）是我们用 Rabin-Karp 算法能做的最好的。也许那个 Wiki 条目不清楚。m

0赞 MAK 8/23/2009

我开始认为维基百科条目在这一点上是完全错误的。它声称复杂度应为 O（n+k）。再次感谢。

2赞 Nick Dandoulakis 8/24/2009

@MAK，请参阅 update2。如果我想出更好的解决方案，我会发布新的更新。

0赞 ire_and_curses 8/23/2009 #2

这是因为子字符串的哈希值在数学上是相关的。计算哈希 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 变得快速？

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

上一个：如何在控制台中制作动态字符串以使用 UTF-8？

下一个：线程似乎按顺序运行线程

使用 Rabin-Karp 搜索字符串中的多个模式

Using Rabin-Karp to search for multiple patterns in a string

评论

评论

评论