Knuth-Morris und Pratt führen einen linearen Zeitalgorithmus für das String-Matching-Problem ein. Eine Übereinstimmungszeit von O (n) wird erreicht, indem ein Vergleich mit einem Element von „S“ vermieden wird, das zuvor im Vergleich mit einem Element des abzugleichenden Musters „p“ beteiligt war. Das heißt, es findet nie ein Backtracking auf der Zeichenfolge „S“ statt
Komponenten des KMP-Algorithmus:
1. Die Präfixfunktion (Π): Die Präfixfunktion Π für ein Muster fasst das Wissen darüber zusammen, wie das Muster mit seiner eigenen Verschiebung übereinstimmt. Diese Informationen können verwendet werden, um eine unnötige Verschiebung des Musters „p“ zu vermeiden. Mit anderen Worten: Dadurch kann ein Zurückverfolgen der Zeichenfolge „S“ vermieden werden.
2. Die KMP-Matches: Suchen Sie mit der Zeichenfolge „S“, dem Muster „p“ und der Präfixfunktion „Π“ als Eingaben das Vorkommen von „p“ in „S“ und geben Sie die Anzahl der Verschiebungen von „p“ zurück, nach denen Vorkommen gefunden werden.
Die Präfixfunktion (Π)
Der folgende Pseudocode berechnet die Präfixfunktion Π:
<strong>COMPUTE- PREFIX- FUNCTION (P)</strong> 1. m ←length [P] //'p' pattern to be matched 2. Π [1] ← 0 3. k ← 0 4. for q ← 2 to m 5. do while k > 0 and P [k + 1] ≠ P [q] 6. do k ← Π [k] 7. If P [k + 1] = P [q] 8. then k← k + 1 9. Π [q] ← k 10. Return Π
Laufzeitanalyse:
Im obigen Pseudocode zur Berechnung der Präfixfunktion wird die for-Schleife von Schritt 4 bis Schritt 10 „m“-mal ausgeführt. Schritt 1 bis Schritt 3 benötigen konstante Zeit. Daher beträgt die Laufzeit der Berechnung der Präfixfunktion O (m).
Beispiel: Berechnen Sie Π für das folgende Muster „p“:
Primärschlüssel und zusammengesetzter Schlüssel in SQL
Lösung:
Initially: m = length [p] = 7 Π [1] = 0 k = 0
Nach sechsmaliger Iteration ist die Berechnung der Präfixfunktion abgeschlossen:
Die KMP-Matches:
Der KMP-Matcher mit dem Muster „p“, der Zeichenfolge „S“ und der Präfixfunktion „Π“ als Eingabe findet eine Übereinstimmung von p in S. Der folgende Pseudocode berechnet die Übereinstimmungskomponente des KMP-Algorithmus:
<strong>KMP-MATCHER (T, P)</strong> 1. n ← length [T] 2. m ← length [P] 3. Π← COMPUTE-PREFIX-FUNCTION (P) 4. q ← 0 // numbers of characters matched 5. for i ← 1 to n // scan S from left to right 6. do while q > 0 and P [q + 1] ≠ T [i] 7. do q ← Π [q] // next character does not match 8. If P [q + 1] = T [i] 9. then q ← q + 1 // next character matches 10. If q = m // is all of p matched? 11. then print 'Pattern occurs with shift' i - m 12. q ← Π [q] // look for the next match
Laufzeitanalyse:
Die for-Schleife, die in Schritt 5 beginnt, läuft „n“-mal, d. h. so lang wie die Länge der Zeichenfolge „S“. Da Schritt 1 bis Schritt 4 konstante Zeiten benötigen, wird die Laufzeit der Schleife davon dominiert. Somit beträgt die Laufzeit der Matching-Funktion O (n).
Beispiel: Gegeben sei eine Zeichenfolge „T“ und ein Muster „P“ wie folgt:
Führen wir den KMP-Algorithmus aus, um herauszufinden, ob „P“ in „T“ vorkommt.
Für 'p' die Präfixfunktion, ? wurde zuvor berechnet und lautet wie folgt:
Lösung:
Initially: n = size of T = 15 m = size of P = 7
Es wurde festgestellt, dass das Muster „P“ in einer Zeichenfolge „T“ komplex ist. Die Gesamtzahl der Schichten, die für die gefundene Übereinstimmung stattgefunden haben, beträgt i-m = 13 - 7 = 6 Schichten.