Der naive Algorithmus wie auch der Knuth-Morris-Pratt-Algorithmus setzen darauf erfolgreich ein Suchmuster zu finden. Das scheint sinnvoll, wenn das Alphabet klein ist und damit die Chance hoch ist, bei der Suche erfolg zu haben. Bei genauerer Betrachtung ist die Chance einen Treffer zu landen jedoch eher gering. Bei einem Unicode-Alphabet können 65336 Zeichen auftreten, die Chance das richtige zu finden ist also 1:65335. In einem ASCII-Text ist die Chance 1:255. Nimmt man nur kleine Buchstaben ist die Chance den richtigen Buchstaben 1:25. Beschränkt man sich auf binäre Zeichen (true oder false) ist die Chance 1:1. Damit die Chance das richtige Zeichen zu finden größer ist, als ein falsches, darf es keine falschen Zeichen gehen.

Hier setzen Boyer-Moore und optimieren die Textsuche für den Regelfall: Sie nutzen die hohe Chance ein falsches Zeichen zu finden, das garantiert, dass man an dieser Stelle das Suchmuster nicht finden wird.

Nehmen wir uns wie beim Knuth-Morris-Pratt-Algorithmus das Wort 'ananas' vor und suchen es im Text „anabellmagananas.“ (Anabell mag Ananas.):

Wenn wir jetzt davon ausgehen, dass wir das Richtige Wort gefunden haben, werden solange wir 'ana' analysiert haben, auch davon überzeugt bleiben. Beim zweiten 'n' werden wir im Text aber das 'b' finden und entsprechend enttäuscht werden. Boyer-Moore macht eine andere Annahme: Ich will das Suchmuster nicht finden und daher schnellst möglich weiter kommen. Hierfür beginnt der Vergleich nicht vorne, sondern hinten:

Nun spielt es zunächst keine Rolle, ob der Vergleich vorne oder hinten fehlschlägt. Wir müssten das Suchmuster nun verschieben, um zu sehen, ob der nächste Buchstabe ein 's' ist:

Aber auch hier können wir uns zunächst das Suchmuster ansehen und schauen, ob wir daraus Erkenntnisse ziehen können. Der erste Vergleich schlägt bei einem 'l' fehl. Das Suchmuster 'ananas' enthält aber kein 'l'. Das bedeutet, dass das Suchmuster vor dem 'l' einfach nicht reinpasst und vor dem 'l' auch kein Anfang des Suchmusters mehr zu finden sein wird, weil sonst das 'l' ja im Suchmuster auftauchen müsste. Und das bedeutet, dass bei einem Mismatch mit einem 'l', das Suchmuster komplett verschoben werden darf:

Wir sind hier mit einem einzigen Vergleich also gleich an Position 6 gelandet. Der nächste Vergleich findet mit einem 'n' statt. Um mit dem nächsten 'n' zu vergleichen muss das Suchmuster zwei Buchstaben verrückt werden:

Zufälligerweise finden wir zwei weitere 'n', können uns also wie beim naiven Algorithmus oder Knuth-Morris-Pratt-Algorithmus nicht nur einen Schritt weiterbewegen, sondern gleich in Zweierschritten durch den Text gehen. Nach 5 Schritten haben wir einen Treffer mit dem 's' gelandet. Nun müssen wir den Vergleich starten.

Würden wir die Ananas hier doch nicht finden, so müssten wir das Suchmuster um eins nach Rechts verschieben und es würde wieder mit dem 's' verglichen werden.

Wir suchen das Suchmuster „ananas“ im Text „anabellmagananasananabolika.“ (Anabell mag Ananas an Anabolika).

Ähnlich des Knuth-Morris-Pratt-Algorithmus muss zunächst das Suchmuster untersucht werden. Damit wir hier nicht mit tausenden Argumenten jonglieren müssen, packen wir zunächst alles, was zum Suchmuster gehört in eine eigene kleine Struktur:

struct Pattern
{
    char const   * Pattern;
    unsigned int   Length;
    int          * Table;
};

Hier können wir die Tabelle speichern, die die Verschiebung im Suchmuster speichert und uns die Länge des Suchmusters merken, so dass wir die sie nicht laufend neu ermitteln müssen.

Wir erzeugen nun ein Suchmuster, indem wir eine Pattern-Struktur anlegen und die Adresse des Suchmusters in die Struktur schreiben:

struct Pattern pat;
pat.Pattern = "ababcabab";

Diesmal sieht unsere Tabelle allerdings anders aus, wir müssen nicht auf die Position im Pattern zugreifen, sondern wir brauchen eine Tabelle, die für alle Zeichen im Alphabet mit der Länge des Patterns initialisiert wird. Anschließend gehen wir die das Suchmuster von links nach rechts durch und tragen für das jeweilige Zeichen die Entfernung zum 's' ein, also die Differenz aus Länge des Patterns und Position des Buchstabens im Pattern.

• Wikipedia: Boyer-Moore-Algorithmus

• Beispielquelltext: boyermoore.c