Turbo-Reverse-Factor

Refinement of Reverse-Factor. It remembers the characters matched in the previuos attempt. It’s complexity id $O(n)$ in time.

Appeared in:

• [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 ↗