Knuth–Morris–Pratt algorithm: Difference between revisions

Revision as of 03:40, 27 October 2019

Revision as of 03:47, 27 October 2019

Line 2:

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 by [[James H. Morris]] and independently discovered by [[Donald Knuth]] "a few weeks later" from automata theory.<ref name=knuth1977>

<ref name=knuth1977>{{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|citeseerx=10.1.1.93.8147}}</ref><ref>

<ref>{{cite journal | last1=Knuth | first1=Donald E. | title=The Dangers of Computer-Science Theory | journal=Studies in Logic and the Foundations of Mathematics | volume=74 | year=1973 | pages=189-195 | doi=10.1016/S0049-237X(09)70357-X}}</ref>

Morris and [[Vaughan Pratt]] published a technical report in 1970.<ref>

<ref>{{cite techreport | last1=Morris | first1=J.H., Jr | last2=Pratt | first2=V. | title=A linear pattern-matching algorithm | number=TR-40 | year=1970 | institution=University of California, Berkeley, Computation Center}}</ref>

The three also published the algorithm jointly in 1977.<ref name=knuth1977></ref> Independently, in 1969, [[Yuri Matiyasevich|Matiyasevich]]<ref>{{cite journal

| language = ru