Die schnellsten Algorithmen zur Mustersuche in Texten sind Varianten des genialen Algorithmus BoMo von Boyer und Moore. Wenn Text und Muster nicht zusammenpassen, verwendet BoMo Tabellen, um die größten zulässigen Verschiebungen zu ermitteln. Eine effiziente Berechnung dieser Tabellen wurde von Knuth angegeben.

Hier wird sowohl auf die den Algorithmen KMP von Knuth, Morris und Pratt, BoMo und ESS zugrundeliegenden Ideen eingegangen, als auch die Implementierung ihrer Verschiebetabellen detailliert beschrieben.

The fastest known algorithms for pattern matching in strings are derivatives of the ingenious algorithm BoMo of Boyer and Moore. On mismatch tables are used by BoMo to ascertain the largest possible pattern shifts. An efficient scheme of computing these tables was given by Knuth.

In this report we recapitulate the key ideas underlying the algorithms KMP of Knuth, Morris and Pratt, BoMo, and ESS, as well as presenting the implementation of their shift tables in detail.