Utilizzando Rabin-Karp per la ricerca di più pattern in una stringa

Question

Secondo il wikipedia su Rabin-Karp algoritmo di string matching, può essere usato per cercare diversi modelli differenti in una stringa, allo stesso tempo, pur mantenendo la complessità lineare. E 'chiaro che questo è fatto facilmente quando tutti i modelli sono della stessa lunghezza, ma ancora non si ottiene come possiamo preservare O (n) la complessità durante la ricerca di modelli con differenti lunghezza contemporaneamente. Qualcuno può far luce su questo?

Modifica (dicembre 2011):

L'articolo di Wikipedia ha da allora sono stati aggiornati e non più sostiene di abbinare molteplici modelli di diversa lunghezza in O (n).

Answer 1

Non sono sicuro se questa è la risposta corretta, ma in ogni caso:
Mentre la costruzione il valore hash, siamo in grado di verificare la presenza di un match nel set di hash stringa. Aka, il corrente valore di hash. La funzione di hash / codice viene generalmente implementato come un ciclo e dentro quel loop possiamo inserire il nostro rapido sguardo in su.
Naturalmente, dobbiamo scegliere m di avere la lunghezza massima della stringa dal set di stringhe.
Aggiornamento: Da 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
[...]

Si calcola corrente hash in passi m. Su ogni passo c'è un temporaneo valore di hash che siamo in grado di guardare in alto (O (1) complessità) nel set di hash. Tutti gli hash avranno le stesse dimensioni, vale a dire a 32 bit.

Aggiornamento 2: un ammortizzato (media) O (n) la complessità?
Sopra ho detto che m deve avere la lunghezza massima della stringa. Si scopre che siamo in grado di sfruttare il contrario.
Con hashing per lo spostamento di ricerca sottostringa e un m fisso formato che possiamo ottenere O (n) la complessità.
Se abbiamo le stringhe di lunghezza variabile possiamo impostare m alla lunghezza minima di stringa. Inoltre, nel set di hash non associamo un hash con l'intera stringa, ma con i primi m-caratteri di esso.
Ora, mentre la ricerca del testo controlliamo se l'hash corrente è nel set di hash ed esaminiamo le stringhe associate per un match.
Questa tecnica aumenterà i falsi allarmi, ma in media ha O (n) la complessità.

Answer 2

E 'perché i valori hash delle stringhe sono correlate matematicamente. Calcolare l'hash H (S, j) (hash dei caratteri a partire dalla posizione j-esimo della stringa S ) calcia O (m) tempo su una stringa di lunghezza m . Ma una volta che avete che, calcolando H (S, j + 1) può essere fatto in tempo costante, perché H (S, j + 1) può essere espresso come un funzione di H (S, j) .

O (m) + O (1) => O (m) , cioè tempo lineare.

Ecco un link dove questo è descritto in dettaglio (si veda ad esempio la sezione "ciò che rende Rabin-Karp veloce?")