按照维基百科条目上拉宾，卡普字符串匹配算法，它可以被用来寻找几个不同的模式在一个字符串在同一时间同时仍然保持线性复杂度。 很显然，当所有的图案都是相同的长度，这是很容易做到，但我仍然没有得到与同时不同长度的模式进行搜索时，我们如何能够保持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）的 （来自串S的第j个位置开始的字符的散列）呈现的长度为m的字符串O（米）的时间。 但是，一旦你有，计算H（S，J + 1）可以在固定时间内完成，因为H（S，J + 1）可以表示为H（S，J）的功能。
O（M）+ O（1）=> O（M），即线性时间。
这里有一个链接在那里，这是更详细的描述（例如参见节“是什么使拉宾，卡普快？”）
文章来源: Using Rabin-Karp to search for multiple patterns in a string
