Boyer-Moore-Algorithmus < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo,
ich glaube, ich habe den BM-Alg. noch nicht ganz verstanden. Hab schon zahlreiche Quellen durchgelesen, aber dort steht immer dasselbe, und zwar:
Stimmt beim Vergleich des Musters mit dem Text von rechts nach links ein Zeichen des Musters nicht mit dem Zeichen des Textes überein ("Bad-Character"), wird im Muster nach dem letzten Vorkommen dieses Bad-Characters gesucht und das Muster soweit verschoben, bis beide Buchstaben übereinander liegen. Existiert dieser Bad-Character nicht im Muster wird das Muster um seine volle Länge nach rechts verschoben.
Nur irgendwie kann das so ja noch nicht ganz stimmen, nehmen wir z.B. folgendes Beispiel
Text: z z a b a b z z
Muster: a b a b
z z a b a b z z
a b a b
^
An dieser Stelle tritt der erste Mismatch auf. Im Text steht ein z, also ein Zeichen, dass nicht im Muster vorkommt. Laut Definition müssen wir in diesem Fall das Muster um seine volle Länge verschieben, also:
z z a b a b z z
a b a b
^ a b a b
^
Und schon haben wir das Muster im String übersehen.
Wo ist mein Fehler?
Vielen Dank schon mal!
(Diese Frage wurde in keinem anderen Forum gestellt.)
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:20 So 18.07.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
