Knuth–Morris–Pratt algorithm: Difference between revisions

Revision as of 19:22, 12 August 2017

Revision as of 11:01, 18 August 2017

Line 4:

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 [[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

| language = ru

| last1 = Матиясевич

Line 24:

| pages = 64–70

| url = http://logic.pdmi.ras.ru/~yumat/Journal/inclusion/inclusion.pdf.gz

}}</ref>{{,}}<ref>Knuth mentions this fact in the errata of his book ''Selected Papers on Design of Algorithms '' : {{quotation|I learned in 2012 that Yuri Matiyasevich had anticipated the linear-time pattern matching and pattern preprocessing algorithms of this paper, in the special case of a binary alphabet, already in 1969. He presented them as constructions for a Turing machine with a two-dimensional working memory.}}</ref> got in 1969 a similar algorithm, coded by a two-dimensional Turing machine, by studying a string pattern matching recognition problem.

==Background==