Content deleted Content added
Tags: Mobile edit Mobile web edit |
Removed line claiming this was the first linear-time text matching algorithm. Regular expression matching dates from 1951 mathematically and several years prior to this in implementations other than KMP. It runs in linear time. The cited article attached to this claim was also removed, given that it totally failed to support the incorrect statement. Tags: Reverted references removed |
||
Line 29:
| 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.
==Background==
|