Content deleted Content added
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 |
Undid revision 987940673 by 216.106.94.95 (talk) regexp matching is not linear in the size of the pattern with technology available at that time |
||
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. This was the first linear-time algorithm for string matching.<ref>{{cite journal
| last1 = Amir | first1 = Amihood
| last2 = Landau | first2 = Gad M.
| last3 = Lewenstein | first3 = Moshe
| last4 = Sokol | first4 = Dina
| doi = 10.1145/1240233.1240242
| issue = 2
| journal = ACM Trans. Algorithms
| page = 19
| title = Dynamic text and static pattern matching
| volume = 3
| year = 2007}}</ref>
==Background==
|