使用拉宾，卡普搜索多个图案中的字符串

Question

按照维基百科上拉宾-卡普字符串匹配算法条目时，它可以是看惯了几种不同的模式在一个字符串在同一时间同时仍然保持线性复杂度。很显然，当所有的图案都是相同的长度，这是很容易做到，但我仍然没有得到与同时不同长度的模式进行搜索时，我们如何能够保持O（n）的复杂性。是否有人可以提供一些线索这光？

编辑（2011年12月）：

在维基百科文章已经被更新，并且不再要求以匹配在O（n）的不同长度的多个图案。

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）时间复杂度。

Answer 2

这是因为该子串的散列值数学相关。计算散列 H（S，j）的（字符从字符串取值的第j个位置开始的散列）开 O（M）时间上的长度的米的字符串。但是，一旦你有，计算 H（S，J + 1）可在恒定的时间内完成，因为 H（S，J + 1）可以被表示为一个 H（S，j）的函数。

O（M）+ O（1）=> O（M），即线性时间。

这里的一个链接其中这更详细地（例如，部分“是什么使拉宾-卡普快？”看到）中描述