Datenstrukturen und Algorithmen
Welche Aussage beschreibt ein Merkmal des Boyer-Moore-Algorithmus zum Suchen eines Musters in einer Zeichenkette richtig?
- AEr vergleicht das Muster beginnend mit seinem letzten Zeichen und nutzt Informationen wie die, dass das nicht passende Textzeichen im Muster nicht vorkommt, um das Muster auf einmal weit zu verschieben
- BEr verschiebt das Muster vom Anfang des Textes jeweils um ein Zeichen und vergleicht jedes Mal alle Zeichen des Musters vom ersten bis zum letzten
- CEr sortiert Text und Muster und findet das Muster dann durch binäre Suche
Antwort und Erläuterung anzeigen
Antwort: A. Er vergleicht das Muster beginnend mit seinem letzten Zeichen und nutzt Informationen wie die, dass das nicht passende Textzeichen im Muster nicht vorkommt, um das Muster auf einmal weit zu verschieben
Der Boyer-Moore-Algorithmus vergleicht das Muster von seinem letzten Zeichen her und berechnet vorab Tabellen, sodass zum Beispiel das gesamte Muster über ein nicht passendes Textzeichen hinweggeschoben werden kann, wenn dieses im Muster gar nicht vorkommt. Bei natürlichsprachlichem Text kann er dadurch viele Zeichen überspringen, ohne sie zu vergleichen. Bei einem Text der Länge n und einem Muster der Länge m braucht das naive Verfahren, das jeweils um ein Zeichen verschiebt und alles vergleicht, im schlechtesten Fall O(nm). Auch der KMP-Algorithmus nutzt Informationen über Fehlvergleiche zum Verschieben, vergleicht aber vom Anfang des Musters her und garantiert selbst im schlechtesten Fall O(n + m).