KMP Muster finden Algorithmus

Question

Ich verstehe den KMP-Algorithmus, dh das Konzept der Speicherung von Wert für übereinstimmende Suffix mit Präfix und dann nicht zurück, wenn in einer Zeichenfolge suchen, wie für ein Muster "abcdabca" Präfix Array wird {0 sein, 0,0,0,1,2,3,1} Ich verstehe, bis {0,0,0,0,1,2,3, _} und dann 'd' an der 4. Stelle nicht mit 'a übereinstimmt ' zu guter Letzt. Und dann sagt der Algo zu arr [j-1] zurückzugehen, wenn j! = 0, ich kann sehen, dass dies uns das richtige Ergebnis gibt, aber ich kann nicht verstehen, warum wir zum vorherigen Element [Daten] für a zurückgehen Verständnisbasis.

Wir gehen zurück, bis wir ein passendes Element oder j == 0 finden, kann ich nicht verstehen, warum wir zurück gehen.

Dank

Answer 1

In meinem eigenen Verständnis, verwenden wir Fehlerfunktion F[i]-0 basierten Index des längsten Präfix darzustellen, die die gleiche wie Suffix der Unterkette ist S[0...i] (für längste, meine ich die längste andere als die gesamte Unterkette selbst)

Von Ihrem OP, ich glaube, Ihre Implementierung oder ein Tutorial 1-basierte verwenden, aber das ist völlig abhängig von Implementierung

folgendes Beispiel: S = abababcabab

würde die Fehlerfunktion wie F = [-1,-1,0,1,2,3,-1,0,1,2,3]

sein Was Sie genau hinschauen kann, ist, was passiert, wenn der Algorithmus zum Zeitpunkt der Verarbeitung ist für S' = ababab???? Failure Funktion Berechnung und F = [-1,-1,0,1,2,3,?,?,?,?,?]

nun das nächste Zeichen c, die Der Algorithmus testet, ob er das bereits bekannte längste Präfix (Suffix) abab anhängen kann, um einen längeren zu erstellen. Der Test schlägt fehl als Präfix ababa! = Suffix ababc, aber was dann?

Dann wird der Algorithmus versuchen, die Longest-Prefix zu suchen (Suffix) der ausgefallenen Longest-Prefix (Suffix) und sieht, was auf dem ein c anhängig wird uns ein Spiel (wenn ja, dann ist es die Antwort).

Dies bedeutet, dass der Algorithmus die Longest-Prefix-Test (Suffix) vonabab die ab ist, und das können wir schnell wissen, weil wir F(abab) = 3 wissen (was wir c und nicht anhängen testen) und wir wissen, F(F(abab)) = F(3) = 1, welches ist die Position von ab.

Das gleiche passiert rekursiv, bis Sie, wie Sie sagten, eine Übereinstimmung finden oder gar keine Übereinstimmung. Das "Springen" der F[], wenn Übereinstimmungen fehlschlagen, implementiert diesen Prozess: Testen Sie das nächste mögliche längste Präfix (Suffix), wenn fehlschlagen, finden Sie die nächste ...