Алгоритм Кнута – Морриса – Пратта

Алгоритм Кнута – Морриса – Пратта
Сорт	Строковый поиск
Структура данных	Нить
Худшая производительность	предварительная обработка + соответствие
Наихудшая пространственная сложность

В информатике алгоритм Кнута-Морриса-Пратта (или алгоритм KMP ) представляет собой алгоритм поиска строк , который ищет вхождения «слова». W внутри основной «текстовой строки» S используя наблюдение о том, что при возникновении несоответствия само слово содержит достаточную информацию, чтобы определить, где может начаться следующее совпадение, таким образом минуя повторную проверку ранее совпавших символов.

Алгоритм теории был придуман Джеймсом Х. Моррисом и независимо открыт Дональдом Кнутом «несколько недель спустя» на основе автоматов . ^[1]^[2] Моррис и Воан Пратт опубликовали технический отчет в 1970 году. ^[3] Все трое также опубликовали алгоритм совместно в 1977 году. ^[1] Самостоятельно в 1969 году Матиясевич ^[4]^[5] обнаружил аналогичный алгоритм, закодированный двумерной машиной Тьюринга, при изучении проблемы распознавания совпадений строковых шаблонов в двоичном алфавите. Это был первый алгоритм сопоставления строк с линейным временем. ^[6]

Фон

Алгоритм сопоставления строк хочет найти начальный индекс m в строке S[] которое соответствует искомому слову W[].

Самый простой алгоритм, известный как « грубый » или «наивный» алгоритм, заключается в поиске совпадения слов по каждому индексу. m, т.е. позиция в искомой строке, соответствующая символу S[m]. На каждой позиции m алгоритм сначала проверяет равенство первого символа искомого слова, т.е. S[m] =? W[0]. Если совпадение найдено, алгоритм проверяет другие символы в искомом слове, проверяя последовательные значения индекса позиции слова. i. Алгоритм извлекает символ W[i] в искомом слове и проверяет равенство выражения S[m+i] =? W[i]. Если все последовательные символы совпадают в W на позиции m, то совпадение будет найдено в этой позиции в строке поиска. Если индекс m достигает конца строки, то совпадений нет, и в этом случае поиск считается «неудачным».

Обычно пробная проверка быстро отклоняет пробное совпадение. Если строки представляют собой равномерно распределенные случайные буквы, то вероятность совпадения символов равна 1 из 26. В большинстве случаев пробная проверка отклонит совпадение по начальной букве. Вероятность того, что первые две буквы совпадут, составляет 1 из 26 (1 из 26^2 шансов на совпадение более 26 возможных букв). Итак, если символы случайны, то ожидаемая сложность поиска строки S[] длины n имеет порядок n сравнений или O ( n ). Ожидаемая производительность очень хорошая. Если S[] составляет 1 миллион символов и W[] составляет 1000 символов, то поиск строки должен завершиться примерно после 1,04 миллиона сравнений символов.

Ожидаемая производительность не гарантирована. Если строки не случайные, то проверка пробная m может потребоваться множество сравнений символов. Худший случай — если две строки совпадают во всем, кроме последней буквы. Представьте, что строка S[] состоит из 1 миллиона символов, все из которых являются A , и что слово W[] состоит из 999 символов A , заканчивающихся последним B. символом Простой алгоритм сопоставления строк теперь будет проверять 1000 символов в каждой пробной позиции, прежде чем отклонять совпадение и продвигать пробную позицию. Простой пример поиска строк теперь потребует около 1000 сравнений символов, умноженных на 1 миллион позиций для 1 миллиарда сравнений символов. Если длина W[] равно k , то производительность в худшем случае равна O ( k ⋅ n ).

Алгоритм KMP имеет лучшую производительность в худшем случае, чем простой алгоритм. KMP тратит немного времени на предварительный расчет таблицы (порядка размера W[], O ( k )), а затем использует эту таблицу для эффективного поиска строки в O ( n ).

Разница в том, что KMP использует информацию о предыдущих совпадениях, чего не делает простой алгоритм. В приведенном выше примере, когда KMP видит, что пробное совпадение не удалось выполнить на 1000-м символе ( i = 999), потому что S[m+999] ≠ W[999], оно будет увеличиваться m на 1, но он будет знать, что первые 998 символов в новой позиции уже совпадают. KMP сопоставил 999 символов A , прежде чем обнаружил несоответствие в 1000-м символе (позиция 999). Продвижение позиции пробного матча m по одному выбрасывает первую A , поэтому KMP знает, что есть 998 символов A , которые соответствуют W[] и не проводит их повторное тестирование; то есть КМП устанавливает i до 998. KMP хранит свои знания в предварительно вычисленной таблице и двух переменных состояния. Когда КМП обнаруживает несоответствие, таблица определяет, насколько увеличится КМП (переменная m) и где возобновится тестирование (переменная i).

Алгоритм КМП

Пример алгоритма поиска

Чтобы проиллюстрировать детали алгоритма, рассмотрим (относительно искусственный) запуск алгоритма, где W = "АБВДАБД" и S = "АВС ABCDAB ABDABCDABDE". В любой момент времени алгоритм находится в состоянии, определяемом двумя целыми числами:

m, обозначающий положение внутри S где предполагаемое совпадение для W начинается,
i, обозначающий индекс текущего рассматриваемого символа в W.

На каждом этапе алгоритм сравнивает S[m+i] с W[i] и приращения i если они равны. Это изображено в начале пробега, как

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456

Алгоритм сравнивает последовательные символы W «параллельным» персонажам S, переходя от одного к другому, увеличивая i если они совпадают. Однако на четвертом этапе S[3] = ' ' не соответствует W[3] = 'D'. Вместо того, чтобы снова начинать поиск в S[1], отметим, что нет 'A' происходит между позициями 1 и 2 в S; следовательно, предварительно проверив все эти символы (и зная, что они соответствуют соответствующим символам в W), шансов найти начало матча нет. Поэтому алгоритм устанавливает m = 3 и i = 0.

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:    ABCDABD
i:    0123456

Это совпадение не соответствует начальному символу, поэтому алгоритм устанавливает m = 4 и i = 0

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:     ABCDABD
i:     0123456

Здесь, i увеличивается до почти полного совпадения "ABCDAB" до i = 6 дает несоответствие в W[6] и S[10]. Однако незадолго до окончания текущего частичного совпадения существовала подстрока "AB" это может быть началом нового совпадения, поэтому алгоритм должен это учитывать. Поскольку эти символы соответствуют двум символам до текущей позиции, эти символы не нужно проверять повторно; алгоритм устанавливает m = 8 (начало начального префикса) и i = 2 (сигнализируя о совпадении первых двух символов) и продолжает сопоставление. Таким образом, алгоритм не только опускает ранее совпавшие символы S ( "AB"), но и ранее совпавшие символы W (префикс "AB").

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:         ABCDABD
i:         0123456

Этот поиск в новой позиции сразу завершается неудачей, потому что W[2] (а 'C') не совпадает S[10] (а ' '). Как и в первом испытании, несоответствие заставляет алгоритм вернуться к началу W и начинает поиск с несовпадающей позиции символа S: m = 10, перезагрузить i = 0.

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:           ABCDABD
i:           0123456

Матч в m=10 немедленно терпит неудачу, поэтому следующий алгоритм пытается m = 11 и i = 0.

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:            ABCDABD
i:            0123456

И снова алгоритм совпадает "ABCDAB", но следующий символ, 'C', не соответствует последнему символу 'D' слова W. Рассуждая, как и раньше, алгоритм устанавливает m = 15, чтобы начать с двухсимвольной строки "AB" до текущей позиции, установите i = 2и продолжите сопоставление с текущей позиции.

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:                ABCDABD
i:                0123456

На этот раз совпадение завершено, и первым символом совпадения является S[15].

Описание псевдокода алгоритма поиска

Приведенный выше пример содержит все элементы алгоритма. На данный момент мы предполагаем существование таблицы «частичного соответствия». T, описанный ниже , который указывает, где нам нужно искать начало нового совпадения при обнаружении несоответствия. Записи T построены так, что если у нас есть совпадение, начинающееся с S[m] это не получается при сравнении S[m + i] к W[i], то следующее возможное совпадение начнется с индекса m + i - T[i] в S (то есть, T[i] — это объем «возврата», который нам нужно сделать после несоответствия). Это имеет два значения: во-первых, T[0] = -1, что указывает на то, что если W[0] есть несоответствие, мы не можем вернуться назад и должны просто проверить следующий символ; и во-вторых, хотя следующее возможное совпадение начнется с индекса m + i - T[i], как и в приведенном выше примере, нам не нужно фактически проверять какие-либо T[i] символы после этого, чтобы продолжить поиск с W[T[i]]. Ниже приведен пример реализации псевдокода алгоритма поиска KMP.

algorithm kmp_search:
    input:
        an array of characters, S (the text to be searched)
        an array of characters, W (the word sought)
    output:
        an array of integers, P (positions in S at which W is found)
        an integer, nP (number of positions)

    define variables:
        an integer, j ← 0 (the position of the current character in S)
        an integer, k ← 0 (the position of the current character in W)
        an array of integers, T (the table, computed elsewhere)

    let nP ← 0

    while j < length(S) do
        if W[k] = S[j] then
            let j ← j + 1
            let k ← k + 1
            if k = length(W) then
                (occurrence found, if only first occurrence is needed, m ← j - k  may be returned here)
                let P[nP] ← j - k, nP ← nP + 1
                let k ← T[k] (T[length(W)] can't be -1)
        else
            let k ← T[k]
            if k < 0 then
                let j ← j + 1
                let k ← k + 1

Эффективность алгоритма поиска

Предполагая предварительное существование таблицы T, часть поиска алгоритма Кнута-Морриса-Пратта имеет сложность O ( n ) , где n — длина S и O — это обозначение big-O . За исключением фиксированных накладных расходов, возникающих при входе в функцию и выходе из нее, все вычисления выполняются в while петля. Чтобы ограничить количество итераций этого цикла; заметить, что T устроено так, что если матч, начавшийся в S[m] не получается при сравнении S[m + i] к W[i], то следующее возможное совпадение должно начинаться с S[m + (i - T[i])]. В частности, следующее возможное совпадение должно произойти с более высоким индексом, чем m, так что T[i] < i.

Этот факт означает, что цикл может выполняться не более 2n раз , поскольку на каждой итерации он выполняет одну из двух ветвей цикла. Первая ветвь неизменно увеличивается i и не меняется m, так что индекс m + i изучаемого в настоящее время характера S увеличивается. Вторая ветка добавляет i - T[i] к m, и, как мы видели, это всегда положительное число. Таким образом, расположение m начала текущего потенциального матча увеличено. При этом отходит вторая ветвь m + i без изменений, для m получает i - T[i] добавлено к нему, и сразу после T[i] присваивается в качестве нового значения i, следовательно new_m + new_i = old_m + old_i - T[old_i] + T[old_i] = old_m + old_i. Теперь цикл заканчивается, если m + i = п ; следовательно, до каждой ветви цикла можно добраться не более n раз, так как они соответственно увеличиваются либо m + i или m, и m ≤ m + i: если m = n , то, конечно, m + i ≥ n , так что, поскольку оно увеличивается не более чем на единицу приращения, мы должны были иметь m + i = n в какой-то момент в прошлом, и, следовательно, в любом случае мы бы закончили.

Таким образом, цикл выполняется не более 2 n раз, показывая, что временная сложность алгоритма поиска равна O ( n ).

Вот еще один способ подумать о времени выполнения: Допустим, мы начинаем соответствовать W и S на позиции i и p. Если W существует как подстрока S в п, тогда W[0..m] = S[p..p+m]. В случае успеха, то есть слово и текст совпадают по позициям ( W[i] = S[p+i]), мы увеличиваем i на 1. При неудаче, то есть слово и текст не совпадают по позициям ( W[i] ≠ S[p+i]), текстовый указатель остается неподвижным, а словесный указатель откатывается на определенную величину ( i = T[i], где T это таблица переходов), и мы пытаемся сопоставить W[T[i]] с S[p+i]. Максимальное количество откатов i ограничен iТо есть, в случае любого сбоя мы можем откатиться назад только на столько, на сколько мы продвинулись до сбоя. Тогда ясно, что время выполнения равно 2 n .

Таблица «Частичное совпадение» (также известная как «функция отказа»)

Цель таблицы — позволить алгоритму не совпадать ни с одним символом S более одного раза. Ключевое наблюдение о природе линейного поиска, которое позволяет этому произойти, заключается в том, что, проверив некоторый сегмент основной строки по начальному сегменту шаблона, мы точно знаем, в каких местах находится новое потенциальное совпадение, которое может продолжиться до текущего. позиция может начинаться до текущей позиции. Другими словами, мы «предварительно ищем» сам шаблон и составляем список всех возможных запасных позиций, которые обходят максимум безнадежных символов, не жертвуя при этом никакими потенциальными совпадениями.

Мы хотим иметь возможность поиска по каждой позиции в W, длина максимально длинного начального сегмента W ведущие к этой позиции (но не включая ее), за исключением полного сегмента, начинающегося с W[0] это просто не совпало; вот насколько далеко нам придется отступить, чтобы найти следующее совпадение. Следовательно T[i] в точности равна длине самого длинного собственного начального сегмента W который также является сегментом подстроки, заканчивающейся на W[i - 1]. Мы используем соглашение, согласно которому пустая строка имеет длину 0. Поскольку несовпадение в самом начале шаблона является частным случаем (нет возможности возврата), мы устанавливаем T[0] = -1, как обсуждается ниже .

Рабочий пример алгоритма построения таблицы

Мы рассматриваем на примере W = "ABCDABD" первый. Мы увидим, что он следует той же схеме, что и основной поиск, и эффективен по тем же причинам. Мы устанавливаем T[0] = -1. Найти T[1], мы должны найти правильный суффикс "A" который также является префиксом шаблона W. Но нет подходящих суффиксов "A", поэтому мы установили T[1] = 0. Найти T[2], мы видим, что подстрока W[0] - W[1] ( "AB") имеет правильный суффикс "B". Однако «B» не является префиксом шаблона. W. Поэтому мы установили T[2] = 0.

Продолжая T[3], мы сначала проверяем правильный суффикс длины 1, и, как и в предыдущем случае, он терпит неудачу. Должны ли мы также проверять более длинные суффиксы? Нет, теперь мы отмечаем, что существует короткий путь для проверки всех суффиксов: допустим, мы обнаружили правильный суффикс , который является правильным префиксом (правильный префикс строки не равен самой строке) и заканчивается на W[2] длиной 2 (максимально возможная); то его первый символ также является правильным префиксом W, следовательно, это сам правильный префикс, который заканчивается на W[1], что, как мы уже определили, не произошло как T[2] = 0 и не T[2] = 1. Следовательно, на каждом этапе действует упрощенное правило: необходимо рассматривать возможность проверки суффиксов заданного размера m+1 только в том случае, если действительный суффикс размера m был найден на предыдущем этапе (т. е. T[x] = m) и не стоит проверять m+2, m+3 и т. д.

Следовательно, нам даже не нужно беспокоиться о подстроках длиной 2, и, как и в предыдущем случае, единственная подстрока длиной 1 не работает, поэтому T[3] = 0.

Переходим к следующему W[4], 'A'. Та же логика показывает, что самая длинная подстрока, которую нам нужно рассмотреть, имеет длину 1, и, как и в предыдущем случае, это не удается, поскольку «D» не является префиксом W. Но вместо установки T[4] = 0, мы можем добиться большего, отметив, что W[4] = W[0], а также, что поиск T[4] подразумевает соответствующее S характер, S[m+4], было несоответствием и, следовательно, S[m+4] ≠ 'A'. Таким образом, нет смысла возобновлять поиск с S[m+4]; мы должны начать на 1 позицию впереди. Это означает, что мы можем изменить шаблон W по длине совпадения плюс один символ, поэтому T[4] = -1.

Учитывая теперь следующий персонаж, W[5], что 'B': хотя при проверке самая длинная подстрока окажется 'A', мы все еще устанавливаем T[5] = 0. Рассуждение аналогично тому, почему T[4] = -1. W[5] сам расширяет совпадение префикса, начатое с W[4], и мы можем предположить, что соответствующий символ в S, S[m+5] ≠ 'B'. Итак, возвращаясь назад W[5] бессмысленно, но S[m+5] может быть 'A', следовательно T[5] = 0.

Наконец, мы видим, что следующий символ в текущем сегменте, начинающемся с W[4] = 'A' было бы 'B', и действительно, это тоже W[5]. Более того, тот же аргумент, что и выше, показывает, что нам не нужно заранее искать W[4] найти сегмент для W[6], так что вот оно и берем T[6] = 2.

Поэтому составляем следующую таблицу:

`i`	0	1	2	3	4	5	6	7
`W[i]`	А	Б	С	Д	А	Б	Д
`T[i]`	-1	0	0	0	-1	0	2	0

Другой пример:

`i`	0	1	2	3	4	5	6	7	8	9
`W[i]`	А	Б	А	С	А	Б	А	Б	С
`T[i]`	-1	0	-1	1	-1	0	-1	3	2	0

Другой пример (немного измененный по сравнению с предыдущим примером):

`i`	0	1	2	3	4	5	6	7	8	9
`W[i]`	А	Б	А	С	А	Б	А	Б	А
`T[i]`	-1	0	-1	1	-1	0	-1	3	-1	3

Еще один более сложный пример:

`i`	00	01	02	03	04	05	06	07	08	09	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24
`W[i]`	П	А	Р	Т	я	С	я	П	А	Т	И		я	Н		П	А	Р	А	С	ЧАС	В	Т	И
`T[i]`	-1	0	0	0	0	0	0	-1	0	2	0	0	0	0	0	-1	0	0	3	0	0	0	0	0	0

Описание псевдокода алгоритма построения таблиц

Пример выше иллюстрирует общую технику сборки стола с минимумом возни. Принцип тот же, что и в общем поиске: большая часть работы уже проделана для достижения текущей позиции, поэтому для выхода из нее нужно сделать совсем немного. Единственная незначительная сложность заключается в том, что правильная логика в конце строки ошибочно дает неправильные подстроки в начале. Это требует некоторого кода инициализации.

algorithm kmp_table:
    input:
        an array of characters, W (the word to be analyzed)
    output:
        an array of integers, T (the table to be filled)

    define variables:
        an integer, pos ← 1 (the current position we are computing in T)
        an integer, cnd ← 0 (the zero-based index in W of the next character of the current candidate substring)

    let T[0] ← -1

    while pos < length(W) do
        if W[pos] = W[cnd] then
            let T[pos] ← T[cnd]
        else
            let T[pos] ← cnd
            while cnd ≥ 0 and W[pos] ≠ W[cnd] do
                let cnd ← T[cnd]
        let pos ← pos + 1, cnd ← cnd + 1

    let T[pos] ← cnd (only needed when all word occurrences are searched)

Эффективность алгоритма построения таблиц

Временная (и пространственная) сложность табличного алгоритма равна $O(k)$ , где $k$ длина W.

Внешний цикл: pos инициализируется значением 1, условие цикла pos < k, и pos увеличивается на 1 на каждой итерации цикла. Таким образом, цикл займет $k-1$ итерации.

Внутренний цикл: cnd инициализируется как 0 и увеличивается не более чем на 1 на каждой итерации внешнего цикла. T[cnd] всегда меньше, чем cnd, так cnd уменьшается как минимум на 1 на каждой итерации внутреннего цикла; условие внутреннего цикла cnd ≥ 0. Это означает, что внутренний цикл может выполняться не более столько раз, сколько выполнился внешний цикл – каждое уменьшение cnd на 1 во внутреннем цикле должно иметь соответствующее увеличение на 1 во внешнем цикле. Поскольку внешний цикл занимает $k-1$ итераций, внутренний цикл может занять не более $k-1$ итераций всего.

В совокупности внешний и внутренний циклы занимают не более $2k-2$ итерации. Это соответствует $O(k)$ временная сложность с использованием нотации Big O.

Эффективность алгоритма КМП

Поскольку обе части алгоритма имеют соответственно сложность O(k) и O(n), сложность всего алгоритма равна O(n + k).

Эти сложности одни и те же, независимо от того, сколько повторяющихся моделей присутствует в W или S.

Варианты

Версия KMP, работающая в режиме реального времени, может быть реализована с использованием отдельной таблицы функций отказа для каждого символа алфавита. Если произошло несоответствие символов $x$ в тексте таблица функций отказа для символа $x$ консультируется по индексу $i$ в образце, в котором произошло несоответствие. Это вернет длину самой длинной подстроки, заканчивающейся на $i$ соответствие префиксу шаблона с добавленным условием, что символ после префикса $x$ . С этим ограничением персонаж $x$ в тексте не нужно снова проверяться на следующем этапе, поэтому между обработкой каждого индекса текста выполняется только постоянное количество операций. ^{[ нужна ссылка ]}. Это удовлетворяет ограничению вычислений в реальном времени.

Алгоритм Бута использует модифицированную версию функции предварительной обработки KMP для поиска лексикографически минимального поворота строки . Функция отказа постепенно рассчитывается по мере вращения струны.

Примечания

^ $m$ длина шаблона, то есть строки, которую мы ищем в тексте длиной $n$

Ссылки

^ Перейти обратно: ^а ^б Кнут, Дональд; Моррис, Джеймс Х.; Пратт, Воган (1977). «Быстрое сопоставление с образцом в строках». SIAM Journal по вычислительной технике . 6 (2): 323–350. CiteSeerX 10.1.1.93.8147 . дои : 10.1137/0206024 .
^ Кнут, Дональд Э. (1973). «Опасности теории информатики». Исследования по логике и основам математики . 74 : 189–195. дои : 10.1016/S0049-237X(09)70357-X . ISBN 978-0-444-10491-5 .
^ Моррис, Дж. Х. младший; Пратт, В. (1970). Линейный алгоритм сопоставления с образцом (Технический отчет). Калифорнийский университет, Беркли, Вычислительный центр. ТР-40.
^ Матиясевич, Юрий (1971). "О распознавании в реальное время отношения вхождения" (PDF) . Записки научных семинаров Ленинградского отделения Математического института им. В.А.Стеклова (in Russian). 20 : 104–114. , translated into English as Матиясевич, Юрий (1973). «Распознавание отношения включения в реальном времени» . Журнал советской математики . 1 : 64–70. дои : 10.1007/BF01117471 . S2CID 121919479 . Архивировано из оригинала 30 апреля 2021 г. Проверено 4 июля 2017 г.
^ Кнут упоминает этот факт в опечатках своей книги « Избранные статьи по проектированию алгоритмов» :
В 2012 году я узнал, что Юрий Матиясевич предвосхитил описанные в этой статье алгоритмы сопоставления с образцом и предварительной обработки образов с линейным временем в частном случае двоичного алфавита еще в 1969 году. Он представил их как конструкции для машины Тьюринга с двумерным рабочая память.
^ Амир, Дружелюбие; Ландау, Гад М.; Левенштейн, Моше; Сокол, Дина (2007). «Динамический текст и сопоставление статического шаблона». АКМ Транс. Алгоритмы . 3 (2): 19. дои : 10.1145/1240233.1240242 . S2CID 8409826 .

Кормен, Томас ; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001). «Раздел 32.4: Алгоритм Кнута-Морриса-Пратта». Введение в алгоритмы (второе изд.). MIT Press и McGraw-Hill. стр. 923–931 . ISBN 0-262-03293-7 . Збл 1047.68161 .
Крошмор, Максим; Риттер, Войцех (2003). Жемчужины стрингологии. Текстовые алгоритмы . Ривер Эдж, Нью-Джерси: World Scientific. стр. 20–25. ISBN 981-02-4897-0 . Збл 1078.68151 .
Шпанковский, Войцех (2001). Анализ среднего случая алгоритмов на последовательностях . Серия Wiley-Interscience по дискретной математике и оптимизации. С предисловием Филиппа Флажоле. Чичестер: Уайли. стр. 15–17, 136–141. ISBN 0-471-24063-Х . Збл 0968.68205 .

Внешние ссылки

Анимация апплета поиска строк
Объяснение алгоритма и пример кода на C++ Дэвида Эппштейна.
Описание алгоритма Кнута-Морриса-Пратта и код C Кристиана Чарраса и Тьерри Лекрока
Объяснение алгоритма с нуля от HW Lang
Подробное описание этапов управления KMP Чу-Чэн Се.
Видео лекции NPTELHRD на YouTube
Видеолекции LogicFirst на YouTube
Доказательство правильности
Преобразование между различными формами алгоритма. Архивировано 7 июля 2023 г. в Wayback Machine.
Алгоритм Кнута-Морриса-Пратта, написанный на C#.
Сложность поиска алгоритма KMP объяснена простым языком

[1] $m$ длина шаблона, то есть строки, которую мы ищем в тексте длиной $n$

[knuth1977-2] Перейти обратно: ^а ^б Кнут, Дональд; Моррис, Джеймс Х.; Пратт, Воган (1977). «Быстрое сопоставление с образцом в строках». SIAM Journal по вычислительной технике . 6 (2): 323–350. CiteSeerX 10.1.1.93.8147 . дои : 10.1137/0206024 .

[3] Кнут, Дональд Э. (1973). «Опасности теории информатики». Исследования по логике и основам математики . 74 : 189–195. дои : 10.1016/S0049-237X(09)70357-X . ISBN 978-0-444-10491-5 .

[4] Моррис, Дж. Х. младший; Пратт, В. (1970). Линейный алгоритм сопоставления с образцом (Технический отчет). Калифорнийский университет, Беркли, Вычислительный центр. ТР-40.

[5] Матиясевич, Юрий (1971). "О распознавании в реальное время отношения вхождения" (PDF) . Записки научных семинаров Ленинградского отделения Математического института им. В.А.Стеклова (in Russian). 20 : 104–114. , translated into English as Матиясевич, Юрий (1973). «Распознавание отношения включения в реальном времени» . Журнал советской математики . 1 : 64–70. дои : 10.1007/BF01117471 . S2CID 121919479 . Архивировано из оригинала 30 апреля 2021 г. Проверено 4 июля 2017 г.

[6] Кнут упоминает этот факт в опечатках своей книги « Избранные статьи по проектированию алгоритмов» :
В 2012 году я узнал, что Юрий Матиясевич предвосхитил описанные в этой статье алгоритмы сопоставления с образцом и предварительной обработки образов с линейным временем в частном случае двоичного алфавита еще в 1969 году. Он представил их как конструкции для машины Тьюринга с двумерным рабочая память.

[7] Амир, Дружелюбие; Ландау, Гад М.; Левенштейн, Моше; Сокол, Дина (2007). «Динамический текст и сопоставление статического шаблона». АКМ Транс. Алгоритмы . 3 (2): 19. дои : 10.1145/1240233.1240242 . S2CID 8409826 .

[примечание 1]

[1]

[2]

[3]

[4]

[5]

[6]

v т и Струны
String metric	Approximate string matching Bitap algorithm Damerau–Levenshtein distance Edit distance Gestalt pattern matching Hamming distance Jaro–Winkler distance Lee distance Levenshtein automaton Levenshtein distance Wagner–Fischer algorithm
String-searching algorithm	Apostolico–Giancarlo algorithm Boyer–Moore string-search algorithm Boyer–Moore–Horspool algorithm Knuth–Morris–Pratt algorithm Rabin–Karp algorithm Raita algorithm Trigram search Two-way string-matching algorithm Zhu–Takaoka string matching algorithm
Multiple string searching	Aho–Corasick Commentz-Walter algorithm
Regular expression	Comparison of regular-expression engines Regular grammar Thompson's construction Nondeterministic finite automaton
Sequence alignment	BLAST Hirschberg's algorithm Needleman–Wunsch algorithm Smith–Waterman algorithm
Data structure	DAFSA Suffix array Suffix automaton Suffix tree Generalized suffix tree Rope Ternary search tree Trie
Other	Parsing Pattern matching Compressed pattern matching Longest common subsequence Longest common substring Sequential pattern mining Sorting String rewriting systems String operations

v т и Дональд Кнут
Publications	The Art of Computer Programming "The Complexity of Songs" Computers and Typesetting Concrete Mathematics Surreal Numbers Things a Computer Scientist Rarely Talks About Selected papers series
Software	TeX Metafont MIXAL (MIX MMIX)
Fonts	AMS Euler Computer Modern Concrete Roman
Literate programming	WEB CWEB
Algorithms	Knuth's Algorithm X Knuth–Bendix completion algorithm Knuth–Morris–Pratt algorithm Knuth shuffle Robinson–Schensted–Knuth correspondence Trabb Pardo–Knuth algorithm Generalization of Dijkstra's algorithm Knuth's Simpath algorithm
Other	Dancing Links Knuth reward check Knuth Prize Knuth's up-arrow notation Man or boy test Quater-imaginary base -yllion Potrzebie system of weights and measures