Informatik Algorithmen – String-Matching und KMP
Karteikarten zum Thema „Informatik“ · 14 Karten · von atrio. Beispiele: Was ist das String-Matching-Problem? · Wie funktioniert der naive String-Matching-Alg…
Karten
14 KartenWas ist das String-Matching-Problem?
Rückseite
Gegeben Text T der Länge n und Muster P der Länge m: Finde alle Vorkommen von P in T.
Wie funktioniert der naive String-Matching-Algorithmus?
Rückseite
Vergleiche P bei jeder Position i in T zeichenweise; bei Mismatch rücke P um eine Position weiter.
Wie lautet die schlimmste Laufzeit der naiven Suche?
Rückseite
O(n·m), beispielsweise bei T='aaaaa...' und P='aaaaab' mit vielen fast vollständigen Treffern.
Was ist die Kernidee des Knuth-Morris-Pratt-Algorithmus?
Rückseite
Bei Mismatch nutze Vorwissen über das Muster, um P nicht um 1, sondern um den größten Border zu verschieben.
Was speichert die Präfixfunktion π[i] im KMP-Algorithmus?
Rückseite
Länge des längsten echten Präfixes von P[0..i], das gleichzeitig Suffix ist (längster Border).
Berechne die Präfixfunktion π für das Muster 'ababaca'.
Rückseite
π = [0,0,1,2,3,0,1] – Index 0 bis 6, jeweils längster Border des Teilstrings.
Was ist ein Border bei String-Matching?
Rückseite
Ein String, der sowohl echte Präfix als auch echte Suffix eines gegebenen Strings ist.
Wie nutzt KMP die π-Funktion während der Suche bei einem Mismatch?
Rückseite
Springe im Muster zurück auf Position π[j-1], Textposition bleibt unverändert – keine Rückwärtsbewegung im Text.
Wie lautet die Laufzeit von KMP für Vorverarbeitung und Suche?
Rückseite
Vorverarbeitung O(m), Suche O(n), insgesamt O(n+m) – linear in Text- und Musterrlänge.
Was berechnet der Z-Algorithmus für einen String S?
Rückseite
Z[i] = Länge des längsten Präfixes von S, das auch Präfix von S[i..n-1] ist.
Worin unterscheidet sich der Z-Algorithmus konzeptionell von KMP?
Rückseite
Z-Algorithmus arbeitet auf dem Text (oder verketteten String), KMP nutzt nur Muster-Informationen für Sprünge.
Bestimme das Z-Array für den String 'aabaac'.
Rückseite
Z = [6,1,0,2,1,0] – Z[0]=n, Z[1]=1 ('a'), Z[3]=2 ('aa'), Rest 0.
Warum vermeidet KMP das Zurückspringen im Text im Gegensatz zur naiven Suche?
Rückseite
Weil die π-Funktion garantiert, dass alle Zeichen links der aktuellen Textposition bereits mit Präfix von P übereinstimmen.
Nenne drei praktische Anwendungen von String-Matching-Algorithmen.
Rückseite
Texteditoren (Suchen/Ersetzen), DNA-Sequenzanalyse in Bioinformatik, Compiler (Lexer für Token-Erkennung), Virenscanner (Signaturerkennung).