Der Knuth–Morris–Pratt-Algorithmus, kurz KMP, ist ein klassischer Algorithmus zum Auffinden eines Patterns in einem Text.
Seine zentrale Idee besteht darin, nach einem Mismatch nicht alle Informationen über bereits übereinstimmende Zeichen zu verwerfen.
Dafür wird das Pattern zunächst analysiert und eine sogenannte LPS-Tabelle aufgebaut.
Was bedeutet LPS?
LPS steht für:
Longest Proper Prefix which is also a Suffix.
Für jedes Präfix des Patterns wird gespeichert, wie lang das längste echte Präfix ist, das gleichzeitig ein Suffix darstellt.
Beispiel:
Pattern: A B A B A C
LPS: 0 0 1 2 3 0
Für ABAB ist AB sowohl Präfix als auch Suffix. Daher lautet der LPS-Wert 2.
Warum ist LPS wichtig?
Wenn nach j erfolgreichen Vergleichen ein Mismatch entsteht, setzt KMP j nicht automatisch auf 0.
Stattdessen:
j = lps[j - 1]
Damit bleibt ein Teil der bereits bekannten Übereinstimmung erhalten.
LPS in TypeScript
function buildLPS(pattern: string): number[] {
const lps = new Array(pattern.length).fill(0);
let length = 0;
let i = 1;
while (i < pattern.length) {
if (pattern[i] === pattern[length]) {
length++;
lps[i] = length;
i++;
} else if (length !== 0) {
length = lps[length - 1];
} else {
lps[i] = 0;
i++;
}
}
return lps;
}
Für:
ABABCABAB
entsteht:
[0, 0, 1, 2, 0, 1, 2, 3, 4]
KMP-Suche
function kmpSearch(text: string, pattern: string): number {
if (pattern.length === 0) return 0;
const lps = buildLPS(pattern);
let i = 0;
let j = 0;
while (i < text.length) {
if (text[i] === pattern[j]) {
i++;
j++;
if (j === pattern.length) {
return i - j;
}
} else if (j !== 0) {
j = lps[j - 1];
} else {
i++;
}
}
return -1;
}
i zeigt auf den Text und j auf das Pattern. Ein entscheidender Punkt ist, dass i bei einem Mismatch nicht zurückgesetzt wird.
Komplexität
Für Textlänge n und Patternlänge m:
LPS: O(m)
Suche: O(n)
Gesamt: O(n + m)
Speicher: O(m)
Eine naive Suche kann im Worst Case dagegen O(n × m) benötigen.
Praktische Anwendungen
KMP und verwandte String-Matching-Konzepte sind nützlich bei:
- Textsuche
- Log-Analyse
- DNA-Sequenzen
- Mustererkennung in Datenströmen
- Sicherheits- und Signaturanalyse
- Algorithmus- und Interviewaufgaben
Bedeutung für technische Interviews
Typische Aufgaben betreffen:
- Substring Search
- Alle Vorkommen eines Patterns
- Aufbau eines LPS Arrays
- Longest Prefix that is also Suffix
- Repeated Substring Pattern
Wichtiger als das Auswendiglernen des Codes ist das Verständnis der Frage, warum LPS Wiederholungen verhindert.
Häufiger Implementierungsfehler
Bei einem Mismatch mit j > 0 darf i nicht sofort erhöht werden.
Nur j wird verändert:
j = lps[j - 1]
Dadurch kann dasselbe Textzeichen gegen eine andere Position des Patterns geprüft werden.
Fazit
KMP ist ein effizienter String-Matching-Algorithmus, der bereits bekannte Informationen über das Pattern nutzt.
Die Vorverarbeitung erzeugt eine LPS-Tabelle, mit deren Hilfe unnötige Vergleiche vermieden werden.
Time Complexity: O(n + m)
Space Complexity: O(m)
Die wichtigste Idee lautet: Ein Mismatch bedeutet nicht, dass alle Informationen aus der vorherigen Übereinstimmung verloren sind.