Können Sie mir die Idee hinter dem String-Matching-Algorithmus von Knuth-Morris-Pratt erzählen?
user
Der String-Matching-Algorithmus Knuth-Morris-Pratt (KMP) ist ein linearer Zeitalgorithmus, der 1977 von Donald Knuth, Vaughan Pratt und James Morris erfunden wurde, um nach Vorkommen eines Musterstrings in einem Textstring zu suchen. Die Hauptidee hinter dem KMP-Algorithmus besteht darin, unnötige Vergleiche zu vermeiden, indem man Informationen über die bereits mit dem Textstring abgestimmte Musterstring nutzt."partial match table"), das ihm sagt, wie viele Zeichen im Muster-String bei einer Fehlanpassung an einer bestimmten Position übersprungen werden sollen, anstatt die Muster-String-Position eine Position nach rechts blind zu bewegen. Um diese Tabelle zu erstellen, konstruiert der Algorithmus zunächst ein Rand-Array, das für jede Position im Muster-String die Länge der längsten korrekten Grenze (d.h. ein Präfix, das auch ein Suffix ist) der Substring-Endung an dieser Position speichert. Das Rand-Array kann in linearer Zeit berechnet werdenmit einem einfachen Algorithmus. Die Fehlerfunktion wird dann wie folgt aus dem Randarray abgeleitet. Für jede Position im Musterstring berechnet der Algorithmus die Länge der längsten korrekten Grenze der Substring-Endung an dieser Position und schaut dann den entsprechenden Wert im Randarray nach. Wenn der Wert Null ist, bedeutet das, dass es keine Grenze gibt, so dass der Fehlerfunktionswert für diese Position Null ist. Andernfalls subtrahiert der Algorithmus die Länge der Grenze vom aktuellenposition und erhält den Index der nächsten möglichen Übereinstimmung in der Muster-String. Dieser Wert wird zum Fehler-Funktionswert für diese Position. Sobald die Fehler-Funktion berechnet wurde, verwendet der Algorithmus es, um nach Vorkommen des Muster-String in der Text-String zu suchen. Es beginnt mit dem Vergleich des ersten Zeichens des Muster-String mit dem ersten Zeichen des Text-String. Wenn sie übereinstimmen, bewegt es sich auf das nächste Zeichen. Wenn sie nicht übereinstimmen, sieht es den Fehler-Funktionswertfür die aktuelle Position im Muster-String und überspringt, dass viele Zeichen vor der Wiederaufnahme des Vergleichs. Dieser Prozess dauert an, bis ein Match gefunden wird oder das Ende des Text-String erreicht wird. Durch die Funktion Fehler, um unnötige Vergleiche überspringen, kann der KMP-Algorithmus nach Vorkommen eines Muster-Strings in einem Text-String in linearer Zeit suchen, mit einer Worst-Case-Laufzeit von O(m + n), wobei m die Länge des Muster-Strings ist und n die Länge des Text-Strings ist.
assistant