KMP-Idee: Präfixfunktion

KMP vorberechnet eine longest-prefix-suffix-Tabelle (pi) für das Muster. Bei Mismatch springt der Algorithmus anhand von pi, ohne das Textfenster blind um 1 zu schieben.

Gesamt $O(n + m)$. Die Idee: bereits gelesene Information nutzen.

Wo gebraucht

Einmalig vorverarbeitete Pattern in Streaming-Scannern und Intrusion-Detection. Baustein für Verständnis von String-Automaten und Regex-Engines.

Vertiefung

KMP merkt sich für jedes bereits betrachtete Musterpräfix, wie weit ein sinnvoller Vergleich nach einem Fehler fortgesetzt werden kann. Die Vorverarbeitung beschreibt dazu Längen geeigneter Randstrukturen innerhalb des Musters. So muss der Textzeiger nach einer teilweisen Übereinstimmung nicht zurückgesetzt werden.

Während der Suche bewegt sich der Textindex nur vorwärts. Der Musterindex kann über vorberechnete Verweise zurückspringen, wobei bereits bestätigte Struktur erhalten bleibt. Vorverarbeitung und Suche benötigen jeweils Arbeit proportional zu ihren Eingabelängen.

Schwierigkeitsstufen

1. Randlängen für kurze Muster schrittweise bestimmen.
2. Einen Fehlvergleich mit dem vorberechneten Rücksprung fortsetzen.
3. Begründen, warum der Text nicht mehrfach rückwärts durchlaufen wird.

Fallstricke

Die Präfixfunktion wird für das Muster, nicht für den durchsuchten Text, aufgebaut. Nach einem Fehler darf ausserdem nicht stets auf null zurückgegangen werden, sonst geht gerade der strukturelle Vorteil verloren.