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]

A Knuth-Morris-Pratt automaton records how much of a fixed pattern matches the suffix of the text seen so far. State $j$ means the longest such prefix has length $j$; reading a symbol moves to the longest compatible prefix state. Reaching state $m$ reports a full length-$m$ match. For pattern aba, state two records suffix ab; reading a completes the match, while reading b falls back to state zero. A dense table for an alphabet of size $R$ uses $O(mR)$ preprocessing and storage, then constant work per text symbol.^[ref]