Content deleted Content added
m formatting fix |
|||
Line 27:
| 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> 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|title=Introductory Chapter: Asphalt and Asphalt Mixture|date=2019-12-11|url=http://dx.doi.org/10.5772/intechopen.88949|work=Asphalt and Asphalt Mixtures|publisher=IntechOpen|isbn=978-1-78984-768-0|access-date=2020-04-21}}</ref>
==Background==
A string-matching algorithm wants to find the starting index <code>m</code> in string <code>S[]</code> that matches the search word <code>W[]</code>.
| |||