Skip to content


It introduces the use of buckets of positions for each character of the alphabet. It works in O(nm)O(nm)-time but has a linear average behavior

Appeared in:

  • [28]: Charras, C., Lecroq, T., Pehoushek, J.D.: A very fast string matching algorithm for small alphabeths and long patterns (extended abstract). In: Farach-Colton [41], pp. 55–64,