Content deleted Content added
→Description of pseudocode for the search algorithm: j and k needed to be swapped, hence the edit |
Citation bot (talk | contribs) Alter: pages. Add: chapter, doi, isbn. Removed URL that duplicated unique identifier. Removed parameters. Formatted dashes. Some additions/deletions were actually parameter name changes. | You can use this bot yourself. Report bugs here. | Activated by Headbomb | via #UCB_webform Tag: use of predatory open access journal |
||
Line 3:
The [[algorithm]] was conceived by [[James H. Morris]] and independently discovered by [[Donald Knuth]] "a few weeks later" from automata theory.<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=
{{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=
Morris and [[Vaughan Pratt]] published a technical report in 1970.<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>
Line 26:
| year = 1973
| pages = 64–70
| doi = 10.1007/BF01117471
| 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> 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.<ref>{{Citation|last=Zhang|first=Haitao|
==Background==
| |||