Two-Way

Linear algorithm in the worst case. Divides the pattern in two factors. It proceeds from left to right while scanning the left factor, and proceeds from right to left while scanning the right factor. It inspects at most $2n − m$ characters.

Appeared in:

• [34]: Crochemore, M., Perrin, D.: Two-way string matching. J. ACM 38(3), 651–675 (1991), http://doi.acm.org/10.1145/116825.116845 ↗