Usando Rabin-Karp para procurar vários padrões em uma string

Question

De acordo com a wikipedia entrada em Rabin-Karp algoritmo cadeia correspondente, pode ser usado para procurar por vários padrões diferentes em uma corda, ao mesmo tempo, mantendo a complexidade linear. É claro que isso é facilmente feito quando todos os padrões são do mesmo comprimento, mas eu ainda não entendo como podemos preservar O (n) a complexidade na busca de padrões com diferentes comprimento simultaneamente. Alguém por favor pode lançar alguma luz sobre isso?

Editar (Dezembro de 2011):

O artigo da Wikipedia já foi atualizado e há reivindicações mais longos para corresponder a vários padrões de diferentes comprimento em O (n).

Answer 1

Eu não tenho certeza se esta é a resposta correta, mas de qualquer maneira:
Enquanto a construção o valor de hash, podemos verificar se há uma correspondência no conjunto de hashes de cordas. Aka, a atual valor de hash. A função hash / code é normalmente implementado como um loop e dentro desse loop podemos inserir o nosso olhar rápido para cima.
É claro, devemos escolher m ter o comprimento máximo da cadeia do conjunto de cordas.
Update: De 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
[...]

Nós calculamos atual hash em etapas m. Em cada etapa há um temporária valor de hash que podemos olhar para cima (O (1) a complexidade) no conjunto de hashes. Todos os hashes terá o mesmo tamanho, ou seja, 32 bit.

Update 2: um amortizado (média) O (n) a complexidade do tempo?
Acima eu disse que m deve ter o comprimento máximo da cadeia. Acontece que podemos explorar o oposto.
Com hashing para o deslocamento substring pesquisa e uma m fixo tamanho que podemos conseguir O (n) a complexidade.
Se temos cadeias de comprimento variável que pode definir m para o comprimento mínimo string. Além disso, no conjunto de hashes não associamos um hash com a corda toda, mas com os primeiros m-caracteres do mesmo.
Agora, enquanto procura o texto vamos verificar se o hash atual é no conjunto de hash e examinamos as cordas associados para uma partida.
Esta técnica irá aumentar os falsos alarmes, mas, em média, tem O (n) a complexidade do tempo.

Answer 2

É porque os valores de hash dos substrings estão relacionadas matematicamente. Calculando o hash H (S, j) (o hash dos caracteres a partir da posição de ordem j de cadeia S ) converte O (m) tempo em uma cadeia de comprimento m . Mas uma vez que você tem isso, computação H (S, j + 1) pode ser feito em tempo constante, porque H (S, j + 1) pode ser expressa como uma função de H (S, j) .

O (m) + O (1) => O (m) , isto é, tempo linear.

Aqui está um link onde isto é descrito em mais detalhes (ver por exemplo a seção "o que faz Rabin-Karp rápido?")