 Knuth-Morris-Pratt algorithm

The Knuth-Morris-Pratt algorithm searches for a pattern using its proper prefix-suffix overlaps. After matching $j$ characters, a mismatch replaces $j$ by the length of the longest proper border of a string for that matched prefix, repeating until the next character can extend it or $j=0$. The text index never moves backward. Precomputing prefix failure links takes $O(m)$ time; during scanning each increase in $j$ can pay for a later decrease, giving $O(n+m)$ total character work and $O(m)$ auxiliary storage. A dense Knuth-Morris-Pratt automaton is a related implementation with alphabet-dependent preprocessing and storage.^[ref]