Knuth–Morris–Pratt algorithm: Difference between revisions

Revision as of 15:50, 18 April 2024

Revision as of 06:35, 28 April 2024

Line 11:

| language = ru

| last1 = Матиясевич

| first1 = Юрий

| title = О распознавании в реальное время отношения вхождения

| journal = Записки научных семинаров Ленинградского отделения Математического института им. В.А.Стеклова

| volume = 20

| year = 1971

| pages = 104–114

Line 21:

| language = en

| last1 = Matiyasevich

| first1 = Yuri

| title = Real-time recognition of the inclusion relation

| journal = Journal of Soviet Mathematics

| volume = 1

| year = 1973

| pages = 64–70

Line 30:

| s2cid = 121919479

| url = http://logic.pdmi.ras.ru/~yumat/Journal/inclusion/inclusion.pdf.gz

| access-date = 2017-07-04

| archive-date = 2021-04-30

| archive-url = https://web.archive.org/web/20210430124227/https://logic.pdmi.ras.ru/~yumat/Journal/inclusion/inclusion.pdf.gz

| url-status = live

}}</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