Boyer-Moore-Algorithmus

Algorithmus:
Der Boyer-Moore-Algorithmus funktioniert wie der Knuth-Morris-Pratt-Algorithmus, nur dass das Muster selbst von rechts nach links verglichen wird. Für den Sprung an die nächste Textposition ergeben sich zwei Strategien, von denen jeweils die günstigere gewählt wird.

Text:                  ...my ice...
Muster:             reminescence
Muster verschoben:        reminescence

1. Bad character Strategie:
Das Muster ''reminescence'' stimmt am Textzeichen ''i'' nicht mehr überein, also kann das Muster bis zum nächsten ''i'' im Muster verschoben werden. Im günstigsten Fall kommt ein Textzeichen im Muster nicht vor, dann wird es um $m$ Zeichen verschoben.

Text:                  ...my ice...
Muster:             reminescence
Muster verschoben:     reminescence

2. Good suffix Strategie:
Das Muster ''reminescence'' stimmt am Textzeichen ''i'' nicht mehr überein, also kann das Muster bis zum nächsten Suffix ''ce'' im Muster verschoben werden.

Komplexität:
Worst Case $O(nm)$, Best Case $O(n/m)$, in der Praxis der schnellste Algorithmus!