根据Rabin-Karp字符串匹配算法的维基百科条目,它可以同时查找一个字符串中的多种不同模式,同时保持线性复杂度。显然,当所有模式具有相同长度时,这很容易实现,但我仍然不明白如何在搜索具有不同长度的模式时保持O(n)复杂度。能否有人解释一下?
编辑(2011年12月):
维基百科文章已更新,不再声称以O(n)的复杂度匹配多个不同长度的模式。
编辑(2011年12月):
维基百科文章已更新,不再声称以O(n)的复杂度匹配多个不同长度的模式。
我不确定这是否是正确答案,但无论如何:
在构造哈希值时,我们可以检查字符串哈希集合中的匹配项。也就是说,当前哈希值。哈希函数/代码通常被实现为循环,在该循环内,我们可以插入快速查找。
当然,我们必须从字符串集合中选择 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
必须具有最大字符串长度。事实证明,我们可以利用相反的情况。m
大小,我们可以实现O(n)的复杂度。m
设置为最小字符串长度。此外,在哈希集合中,我们不是将哈希与整个字符串相关联,而是与其前m个字符相关联。这是因为子字符串的哈希值在数学上是相关的。计算从字符串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快?”部分)