Knuth–Morris–Pratt algorithm: Difference between revisions

Revision as of 16:15, 17 October 2017

Revision as of 21:29, 22 October 2017

Line 2:

<!--If you are thinking of adding an implementation of this algorithm in a particular language, think again. See the talk page.-->

In [[computer science]], the '''Knuth–Morris–Pratt [[string searching algorithm]]''' (or '''KMP algorithm''') searches for occurrences of a "word" <code>W</code> within a main "text string" <code>S</code> 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. The time complexity of the search algorithm is O(n), where n is the length of the string.

The [[algorithm]] was conceived in 1970 by [[Donald Knuth]] and [[Vaughan Pratt]], and independently by [[James H. Morris]]. The three published it jointly in 1977.<ref>{{cite journal|last1=Knuth|first1=Donald|last2=Morris|first2=James H.|last3=Pratt|first3=Vaughan|title=Fast pattern matching in strings|journal=SIAM Journal on Computing|date=1977|volume=6|issue=2|pages=323–350|doi=10.1137/0206024|url=http://epubs.siam.org/doi/abs/10.1137/0206024}}</ref> Independently, [[Yuri Matiyasevich|Matiyasevich]]<ref>{{cite journal