= Knuth-Morris-Pratt automaton
{c}
= KMP automaton
{c}
{synonym}
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.https://raw.githubusercontent.com/kevin-wayne/algs4/master/src/main/java/edu/princeton/cs/algs4/KMP.java[Construction loops and search state update]{ref}
Back to article page
