Boyer-Moore String Matching - Gute Suffix-Verschiebung

Question

Ich verstehe die Bad-Symbol-Tabelle. In der guten Suffix-Tabelle, sollte nicht die Entfernung als die Entfernung vom äußersten rechten Muster des Musters bis zum Ende des Mustertextes berechnet werden? Sollte in diesem Fall die untere Tabelle nicht alle Abstände (d2) wie 1 haben (mit Ausnahme des letzten Eintrags, der 5 wäre), weil das gleiche Muster unmittelbar links davon verfügbar wäre?

Auf ähnliche Begriffe, nie als auch das unten stehende Tabelle verstanden. Irgendeine Hilfe?

Referenz:

Frage - Seite 6 Frage 7.

---

Antwort - Seite 11

---

Das Design und die Analyse von Computer algorithms- Anany Levitin (https://umutzafer.files.wordpress.com/2012/01/solu7.pdf)

Text - The design and analysis of computer algorithms- Anany Levitin (Seite 263)

Answer 1

Die gute Suffixregel ist für eine Instanz des bereits abgestimmten Suffix , wo das vorherige Zeichen unterscheidet. Im Falle des "guten Suffix" 00 in Ihrer ersten Tabelle sucht die Schicht beispielsweise nach einer Instanz 00, der kein 0 vorangestellt ist.

Warum? Weil wir wissen, dass die 0 vor dem "guten Suffix" nicht übereinstimmte; sonst würden wir nicht versuchen, uns zu verschieben.

In der zweiten Tabelle kann keine solche Instanz gefunden werden. Stattdessen suchen wir nach einem plausiblen Präfix des Musters, das mit einem Suffix des "guten Suffix" übereinstimmt.