Knuth–Morris–Pratt algorithm: Difference between revisions

Revision as of 19:31, 28 May 2020

Revision as of 20:11, 28 May 2020

Line 28:

| 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>{{cn|date=Maycite 2020}}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==