"Good-Suffix-Rule"

Die "Good-Suffix-Rule" arbeitet ähnlich wie die ganz am Anfang vorgestellte "noch bessere Methode". Trifft der Algorithmus beim Vergleichen auf ein Mismatch, so schaut er in einem beim Preprocessing erstellten Array (L'[]) nach, ob die Zeichen, die übereinstimmten (also ein Suffix des Suchmusters; wir vergleichen ja von rechts nach links) im Suchmuster noch einmal vorkommen. Ist dies der Fall, so schieben wir das Suchmuster so weit nach rechts, bis das rechteste erneute Vorkommen dieses Suffix unterhalb der bereits verglichenen Zeichen im Text liegt.
Wenn allerdings im ganzen Suchmuster keine Kopie dieses Suffix mehr vorkommt, so schauen wir im ebenfalls beim Preprocessing erstellten Array l'[] nach, ob in der bereits verglichenen Sequenz ein Suffix vorkommt, das gleichzeitig auch im Präfix des Suchmusters vorkommt. Ist dies der Fall, dann schieben wir das Suchmuster so weit nach rechts, bis dieses Präfix unter dem gleichartigen Vorkommen des Suffix im Text liegt. Gibt es auch hier kein passendes Vorkommen, schieben wir das Suchmuster ganz an der momentanen Position vorbei. Also um n + 1 Zeichen, bei einer Länge von n + 1
Sollte ein Vorkommen des kompletten Suchmusters im Text gefunden worden sein (Treffer), verfahren wir genau so, allerdings mit dem größten Suffix im Suchmuster, das gleichzeitig Präfix ist.
In dem Fall, daß gleich der erste Vergleich ein Mismatch ist, schieben wir das Suchmuster um eine Stelle nach rechts.

L'[] und l'[] für das Beispiel-Suchmuster:

l'[pos] := Länge des längsten Suffix in Muster[pos..n], das auch Präfix ist.
L'[pos] := Rechtes Ende der rechtesten Kopie von Muster[pos..n].

Das Beispiel:

Die Frage, ob die "Good-Suffix-Rule" immer korrekt arbeitet läßt sich so beantworten: Würde die Regel an einem Vorkommen des Suchmusters vorbeischieben, hieße dies, daß in L'[] nicht immer das rechteste passende Suffix eingetragen wurde. Dies würde der Definition von L' widersprechen.
Bezüglich l'[] gilt: Würde die Regel an einem Vorkommen des Suchmusters vorbeischieben, hieße dies, daß ein größeres Suffix im Suchmuster existiert als das gerade verglichene. Dann hätten wir aber den entsprechenden L'-Wert nehmen können und wären gar nicht erst zum l'-Wert übergegangen. Übrigens gilt auch hier wieder: Der orginal Boyer-Moore Algorithmus benutzt eine schwächere Version der "Good-Suffix-Rule". Deswegen auch die Ticks (') an L und l.
Das Effiziente Berechnen der Arrays L'[] und l'[] ist das Thema der nächsten beiden Folien.