String-Matching on Ordered ALphabet

It uses constant extra space and achieves a linear time complexity. It inspects at most $6n + 5$ characters.

Appeared in:

• [32]: Crochemore, M.: String-matching on ordered alphabets. Theor. Comput. Sci. 92(1), 33–47 (1992), http://dx.doi.org/10.1016/0304-3975(92)90134-2 ↗