= Knuth-Morris-Pratt algorithm
{c}
= KMP algorithm
{c}
{synonym}
= KMP
{c}
{synonym}
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.https://raw.githubusercontent.com/kevin-wayne/algs4/master/src/main/java/edu/princeton/cs/algs4/KMP.java[Sedgewick and Wayne, KMP.java, class documentation and DFA construction]{ref}
Back to article page
