 Knuth-Morris-Pratt automaton

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]