Content deleted Content added
m →Variants: Actually link to the proper algorithm |
correction to historical details |
||
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 [[Vaughan Pratt]] and published in 1970
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|citeseerx=10.1.1.93.8147}}</ref> Independently, in 1969, [[Yuri Matiyasevich|Matiyasevich]]<ref>{{cite journal▼
<ref>{{cite techreport | last1=Morris | first1=J.H., Jr | last2=Pratt | first2=V. | title=A linear pattern-matching algorithm | number=TR-40 | institution=University of California, Berkeley, Computation Center}}</ref>
and independently discovered by [[Donald Knuth]] "a few weeks later" from automata theory.
<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>
▲
| language = ru
| last1 = Матиясевич
| |||