Algorithmen und Datenstrukturen · Senior · Frage 22 von 75
Wie erreicht KMP eine String-Suche in O(n + m)?
- 1Es hasht vorab jeden Teilstring des Texts
- 2Eine Präfixfunktion sagt, wie weit man verschiebt, ohne Text erneut zu lesen
- 3Es sortiert die Zeichen des Texts und sucht das Muster binär
Antwort zeigen
Richtige Antwort: Eine Präfixfunktion sagt, wie weit man verschiebt, ohne Text erneut zu lesen
Erklärung
Für jede Position des Musters speichert die Präfixfunktion die Länge des längsten echten Präfixes, das zugleich ein Suffix ist. Bei einer Abweichung springt das Muster um diesen Betrag, der Textzeiger geht also nie zurück.