Content deleted Content added
m Made use of n and k in this section consistent with following sections |
|||
Line 29:
}}</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>.
| |||