Rabin-Karp unter Verwendung für mehrere Muster in einer Zeichenfolge suchen

Question

Nach dem Wikipedia-Eintrag auf Rabin-Karp String-Matching-Algorithmus, kann es sein, suchen mehr unterschiedlichen Muster in einem String gleichzeitig verwendet werden, während immer noch lineare Komplexität beibehalten wird. Es ist klar, dass dies leicht geschehen, wenn alle Muster der gleichen Länge sind, aber ich immer noch nicht, wie wir O (n) Komplexität bei der Suche nach Mustern mit unterschiedlicher Länge gleichzeitig erhalten können. Kann jemand bitte vergießen dies etwas Licht auf?

Edit (Dezember 2011):

Der Wikipedia Artikel wurde seit aktualisiert und keine Ansprüche mehr mehrere Muster unterschiedlicher Länge in O (n).

übereinstimmen

Answer 1

Ich bin mir nicht sicher, ob dies die richtige Antwort ist, aber trotzdem:
Während der Konstruktion , um den Hash-Wert, können wir für eine Übereinstimmung in dem Satz von String-Hashes überprüfen. Aka, die Strom Hashwert. Der Hash-Funktion / Code wird in der Regel als eine Schleife implementiert und innerhalb dieser Schleife können wir unsere kurzen Blick nach oben ein.
Natürlich müssen wir m haben die maximale Stringlänge von dem Satz von Saiten holen.
Update: aus 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
[...]

Wir berechnen Strom Hash in m Schritten. Auf jedem Schritt gibt es ein temporären Hash-Wert, den wir sehen können (O (1) Komplexität) in dem Satz von Hashes. Alle Hashes die gleiche Größe haben, also 32 Bit.

Update 2: ein abgeschrieben (Durchschnitt) O (n) Zeit Komplexität?
Above ich sagte, dass m die maximale Stringlänge haben muss. Es stellt sich heraus, dass wir das Gegenteil ausnutzen können.
Mit Hashing zum Verschieben String-Suche und eine feste m Größe können wir O (n) Komplexität erreichen.
Wenn wir Zeichenfolge variabler Länge haben, können wir m auf die minimale String-Länge eingestellt. Zusätzlich kann in dem Satz von Hashes assoziieren wir nicht einen Hash mit der ganzen Saite aber mit den ersten m-Zeichen davon.
Jetzt, während die Textsuche überprüfen wir, ob die aktuelle Hash in dem Hash-Set ist und wir untersuchen die zugehörigen Saiten für ein Spiel.
Diese Technik wird den Fehlalarme erhöhen, aber im Durchschnitt hat O (n) Zeit Komplexität.

Answer 2

Es ist, weil die Hash-Werte des Teils mathematisch verwendet sind. Berechnen des Hash H (S, J) (der Hash-Codierung der Zeichen aus der j-ten Position der Zeichenkette ausgehend S ) hat O (m) Zeit auf einen String der Länge m . Aber sobald Sie haben, dass die Berechnung H (S, j + 1) in konstanter Zeit durchgeführt werden, da H (S, j + 1) kann als ausgedrückt werden Funktion von H (S, j) .

O (m) + O (1) => O (m) , d.h. lineare Zeit.

Hier ist ein Link wo dies wird detaillierter (siehe zB Abschnitt „Was macht Rabin-Karp schnell?“) beschrieben