Erklären Sie das Funktionsprinzip des Knuth-Morris-Pratt-Algorithmus zur Suche nach Teilstrings.
sobes.tech KI
Antwort von AI
Der Knuth-Morris-Pratt-Algorithmus (KMP) ist dafür ausgelegt, eine Teilzeichenkette in einer Zeichenkette in linearer Zeit zu suchen, indem wiederholte Zeichenvergleiche vermieden werden.
Die Hauptidee ist, vorab für die Teilzeichenkette ein Präfix-Funktionsarray (oder "π-Array") zu berechnen, das zeigt, wie viele Zeichen mit dem Anfang der Teilzeichenkette bei einem fehlgeschlagenen Vergleich übereinstimmen. Dies ermöglicht es, bei einer Nichtübereinstimmung nicht zum Anfang der ursprünglichen Zeichenkette zurückzukehren, sondern die Teilzeichenkette um die optimale Anzahl an Positionen zu verschieben.
Beispiel:
- Text: "ABABDABACDABABCABAB"
- Suche nach der Teilzeichenkette: "ABABCABAB"
Der Algorithmus erstellt zunächst die Präfix-Funktion für die Teilzeichenkette, durchläuft dann den Text und vergleicht die Zeichen. Bei Nichtübereinstimmung verwendet er die Präfix-Funktion, um zu bestimmen, ab welchem Zeichen der Teilzeichenkette die Vergleichsoperation fortgesetzt werden soll, ohne von Anfang an zu beginnen.
Dies gewährleistet eine Komplexität von O(n + m), wobei n die Länge des Textes ist, m die Länge der Teilzeichenkette, was effizienter ist als die naive Suche.