Skip to content
Exact Online String Matching

Turbo-Boyer-Moore

Improvement of Boyer-Moore. It remembers characters inspected in the previous attempt. It performs at most 2n2n character inspections.

Appeared in:

  • [53]: Finkel, A., Jantzen, M. (eds.): STACS 92, 9th Annual Symposium on Theoretical Aspects of Computer Science, Cachan, France, February 13-15, 1992, Proceedings, Lecture Notes in Computer Science, vol. 577. Springer (1992)
  • [33]: Crochemore, M., Czumaj, A., Gasieniec, L., Jarominek, S., Lecroq, T., Plandowski, W., Rytter, W.: Speeding up two string-matching algorithms. Algorithmica 12(4/5), 247–267 (1994), http://dx.doi.org/10.1007/BF01185427 ↗