Knuth–Morris–Pratt algorithm

<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, the Knuth–Morris–Pratt algorithm (or KMP algorithm) is a <a href="/facts/String-searching_algorithm/RCvwDRle">string-searching algorithm</a> that searches for occurrences of a "word" W within a main "text string" S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters.
</p><p>The <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> was conceived by <a href="/facts/James_H._Morris/HaFJpDbE">James H. Morris</a> and independently discovered by <a href="/facts/Donald_Knuth/GozNzDM6">Donald Knuth</a> "a few weeks later" from <a href="/facts/Automata_theory/Q6BmPv63">automata theory</a>.
Morris and <a href="/facts/Vaughan_Pratt/w8XlQrpl">Vaughan Pratt</a> published a technical report in 1970.
The three also published the algorithm jointly in 1977. Independently, in 1969, <a href="/facts/Yuri_Matiyasevich/jBom4cJo">Matiyasevich</a> discovered a similar algorithm, coded by a two-dimensional Turing machine, while studying a string-pattern-matching recognition problem over a binary alphabet.  This was the first linear-time algorithm for string matching.
</p>

Knuth–Morris–Pratt algorithm open-in-new

Knuth–Morris–Pratt algorithm