Morris-Pratt

First linear algorithm scanning the text and the pattern from left to right. It derives from Brute-Force. Preprocessing of the pattern in $O(m)$-time and -space.

Appeared in:

• [80]: Morris, Jr, J.H., Pratt, V.R.: A linear pattern-matching algorithm. Report 40, University of California, Berkeley (1970)