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

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

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

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

当然，我们必须

m

从字符串集中选择最大字符串长度。

更新： 从Wikipedia，

[...]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）complexity）。所有哈希将具有相同的大小，即32位。

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

上面我说过

m

必须有最大的字符串长度。事实证明，我们可以利用相反的东西。
通过使用散列来移动子字符串搜索并使用固定

m

大小的哈希，我们可以实现O（n）复杂度。

如果我们有可变长度的字符串，我们可以设置

m

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

此技术将增加虚假警报，但平均而言，它具有O（n）时间复杂度。