Verwenden von Rabin-Karp zum Suchen nach mehreren Mustern in einer Zeichenfolge

Question

Gemäß dem wikipedia entry Rabin-Karp String-Matching-Algorithmus kann es verwendet werden, um mehrere verschiedene Muster in einer Zeichenfolge gleichzeitig zu suchen, während die lineare Komplexität beibehalten wird. Es ist klar, dass dies leicht gemacht wird, wenn alle Muster die gleiche Länge haben, aber ich bekomme immer noch nicht, wie wir O (n) -Komplexität bewahren können, wenn wir gleichzeitig nach Mustern mit unterschiedlicher Länge suchen. Kann jemand bitte etwas Licht darauf werfen?

Edit (Dezember 2011):

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

Answer 1

Ich bin mir nicht sicher, ob dies die richtige Antwort ist, aber trotzdem:

Während den Hash-Wert konstruieren, können wir für eine Übereinstimmung in dem Satz von String-Hashes überprüfen. Aka, der aktuelle Hash-Wert. Die Hash-Funktion/Code wird normalerweise als eine Schleife implementiert und innerhalb dieser Schleife können wir unsere schnelle Suche einfügen.

Natürlich müssen wir m auswählen, um die maximale Stringlänge aus der Menge der Strings zu haben.

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 aktuellen Hash in m Schritten. Für jeden Schritt gibt es einen temporären Hash-Wert, den wir in der Menge der Hashes nachschlagen können (O (1) -Komplexität). Alle Hashes haben die gleiche Größe, dh 32 Bit.

Update 2: eine abgeschrieben (Durchschnitt) O (n) Zeit Komplexität?

Oben habe ich gesagt, dass m die maximale Stringlänge haben muss. Es stellt sich heraus, dass wir das Gegenteil ausnutzen können.
Mit hashing for shifting substring search und einer festen m Größe können wir O (n) Komplexität erreichen.

Wenn wir Strings variabler Länge haben, können wir m auf die minimale Stringlänge setzen. Außerdem ordnen wir in der Menge der Hashes keinen Hash mit der gesamten Zeichenfolge zu, sondern mit den ersten m-Zeichen davon.
Jetzt, während wir den Text suchen, überprüfen wir, ob der aktuelle Hash im Hash-Set ist und untersuchen die zugehörigen Zeichenfolgen für eine Übereinstimmung.

Diese Technik erhöht die Fehlalarme, hat aber im Durchschnitt eine (n) Zeitkomplexität.

Answer 2

Es ist, weil die Hash-Werte der Teilstrings mathematisch verwandt sind. Berechnen des Hash H (S, J) (der Hash-Codierung der Zeichen aus der j-ten Position der Zeichenkette beginnen S) hat O (m) Zeit auf einem String der Länge m. Aber sobald Sie das haben, kann die Berechnung H (S, j + 1) in konstanter Zeit erfolgen, weil H (S, j + 1) kann als eine Funktion von H (S, j) ausgedrückt werden .

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

Here's a link wo dies näher beschrieben wird (siehe zum Beispiel den Abschnitt „Was macht Rabin-Karp schnell?“)