Skip-Search

It introduces the use of buckets of positions for each character of the alphabet. It works in $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, http://dx.doi.org/10.1007/BFb0030780 ↗