В информатике , то Кнута-Морриса-Пратта строка-поиска алгоритма (или KMP алгоритм ) ищет вхождения «слово» W
в главном «текстовая строка» S
, используя наблюдение , что , когда происходит рассогласование, само слово воплощает в себе достаточно информации чтобы определить, где может начаться следующее совпадение, минуя повторную проверку ранее сопоставленных символов.
Класс | Строковый поиск |
---|---|
Структура данных | Нить |
Наихудшая производительность | Θ (m) предварительная обработка + Θ (n) сопоставление [примечание 1] |
Сложность пространства в наихудшем случае | Θ (м) |
Алгоритм был задуман Джеймсом Х. Моррис и независимо друг от друга обнаружили Дональда Кнута «через несколько недель» от теории автоматов . [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 2 (1 из 676). Таким образом, если символы случайны, то ожидаемая сложность поиска в строке 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 ( п ).
Разница в том, что KMP использует информацию о предыдущем совпадении, чего не делает простой алгоритм. В приведенном выше примере, когда KMP обнаруживает, что пробное совпадение не выполнено на 1000-м символе ( i
= 999), потому что S[m+999] ≠ W[999]
оно будет увеличиваться m
на 1, но будет знать, что первые 998 символов в новой позиции уже совпадают. KMP сопоставил 999 символов A, прежде чем обнаружил несоответствие на 1000-м символе (позиция 999). Выросшая позиция матча пробной m
один выбрасывает первый A , так что KMP знает , что есть 998 A символов , которые совпадают W[]
и не их повторные испытания; то есть KMP устанавливается i
в 998. KMP сохраняет свои знания в предварительно вычисленной таблице и двух переменных состояния. Когда KMP обнаруживает несоответствие, таблица определяет, на сколько KMP увеличится (переменная m
) и где будет возобновлено тестирование (переменная i
).
Алгоритм KMP
Пример алгоритма поиска
Чтобы проиллюстрировать детали алгоритма, рассмотрим (относительно искусственный) запуск алгоритма, где W
= "ABCDABD" и S
= "ABC ABCDAB ABCDABCDABDE". В любой момент времени алгоритм находится в состоянии, определяемом двумя целыми числами:
m
, обозначающий позицию, вS
которой начинается предполагаемый матч дляW
,i
, обозначающий индекс текущего рассматриваемого символа вW
.
На каждом шаге алгоритм сравнивает S[m+i]
с W[i]
и приращения , i
если они равны. Это изображено в начале пробега, как
1 2 м: 01234567890123456789012S: ABC ABCDAB ABCDABCDABDE W: ABC D ABD i: 012 3 456
Алгоритм сравнивает последовательные символы W
с «параллельными» символами S
, переходя от одного к другому, увеличивая их, i
если они совпадают. Однако на четвертом шаге S[3] = ' '
не совпадает W[3] = 'D'
. Вместо того, чтобы снова начинать поиск с S[1]
, мы отмечаем, что 'A'
между позициями 1 и 2 в S
; следовательно, предварительно проверив все эти символы (и зная, что они совпадают с соответствующими символами в W
), нет никаких шансов найти начало совпадения. Следовательно, алгоритм устанавливает m = 3
и i = 0
.
1 2 м: 01234567890123456789012S: ABC ABCDAB ABCDABCDABDE W: A BCDABD i: 0 123456
Это совпадение не выполняется для начального символа, поэтому алгоритм устанавливает m = 4
иi = 0
1 2 м: 01234567890123456789012S: ABC ABCDAB ABCDABCDABDE W: ABCDAB D i: 012345 6
Здесь i
увеличивается почти полное совпадение "ABCDAB"
до i = 6
несовпадения W[6]
и S[10]
. Однако непосредственно перед концом текущего частичного совпадения была эта подстрока, "AB"
которая могла быть началом нового совпадения, поэтому алгоритм должен это учитывать. Поскольку эти символы совпадают с двумя символами, предшествующими текущей позиции, повторная проверка этих символов не требуется; алгоритм устанавливает m = 8
(начало начального префикса) и i = 2
(сигнализируя о совпадении первых двух символов) и продолжает сопоставление. Таким образом, алгоритм не только пропускает ранее сопоставленные символы S
( "AB"
), но также и ранее сопоставленные символы W
(префикса "AB"
).
1 2 м: 01234567890123456789012S: ABC ABCD AB ABCDABCDABDE W: AB C DABD i: 01 2 3456
Этот поиск в новой позиции немедленно завершается ошибкой, потому что W[2]
(а 'C'
) не соответствует S[10]
(а ' '
). Как и в первом испытании, несоответствие приводит к тому, что алгоритм возвращается к началу W
и начинает поиск с позиции несовпадающего символа S
:, m = 10
reset i = 0
.
1 2 м: 01234567890123456789012S: ABC ABCDAB ABCDABCDABDE W: A BCDABD i: 0 123456
Совпадение at m=10
немедленно завершается ошибкой, поэтому алгоритм затем пытается m = 11
и i = 0
.
1 2 м: 01234567890123456789012S: ABC ABCDAB ABCDAB C DABDE W: ABCDAB D i: 012345 6
И снова алгоритм совпадает "ABCDAB"
, но следующий символ 'C'
,, не совпадает с последним символом 'D'
слова W
. Рассуждая, как и раньше, алгоритм устанавливает m = 15
, чтобы начать с двухсимвольной строки, "AB"
ведущей к текущей позиции, установить i = 2
и продолжить сопоставление с текущей позиции.
1 2 м: 01234567890123456789012S: ABC ABCDAB ABCD ABCDABD E 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.
алгоритм kmp_search : input : массив символов, S (текст для поиска) массив символов, W (искомое слово) вывод : массив целых чисел, P (позиции в S, в которых находится W) целое число, nP (количество позиций) определить переменные : целое число, j ← 0 (позиция текущего символа в S) целое число, k ← 0 (позиция текущего символа в W) массив целых чисел, T (таблица, вычисленная в другом месте) пусть nP ← 0 в то время как jdo, если W [k] = S [j], тогда пусть j ← j + 1, пусть k ← k + 1, если k = length (W), то (вхождение найдено, если требуется только первое вхождение, здесь может быть возвращено m ← j - k) пусть P [nP] ← j - k, nP ← nP + 1 пусть k ← T [k] (T [length (W)] не может быть -1) иначе пусть k ← T [k] если k <0, то пусть j ← j + 1 пусть k ← k + 1
Эффективность алгоритма поиска
Если предположить , что предварительное существование таблицы T
, поиск часть алгоритма Кнута-Морриса-Пратта имеет сложность O ( п ) , где п представляет длину S
и вывода является большой-O обозначения . За исключением фиксированных накладных расходов, возникающих при входе в функцию и выходе из нее, все вычисления выполняются в while
цикле. Ограничить количество итераций этого цикла; Наблюдайте, что T
это построено таким образом, что если совпадение, которое началось в, S[m]
не удается при сравнении S[m + i]
с W[i]
, то следующее возможное совпадение должно начаться в S[m + (i - T[i])]
. В частности, следующее возможное совпадение должно произойти с индексом выше m
, чем , чтобы T[i] < i
.
Этот факт означает, что цикл может выполняться не более 2 n раз, поскольку на каждой итерации он выполняет одну из двух ветвей в цикле. Первая ветвь неизменно увеличивается 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 ; следовательно, каждая ветвь цикла может быть достигнута не более 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
at p, то 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, м + 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] | А | B | C | D | А | B | D | |
T[i] | -1 | 0 | 0 | 0 | -1 | 0 | 2 | 0 |
Другой пример:
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
W[i] | А | B | А | C | А | B | А | B | C | |
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] | А | B | А | C | А | B | А | B | А | |
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] | п | А | р | Т | я | C | я | п | А | Т | E | я | N | п | А | р | А | C | ЧАС | U | Т | E | |||
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 |
Описание псевдокода для алгоритма построения таблиц.
Пример выше иллюстрирует общую технику сборки стола с минимумом хлопот. Принцип заключается в общем поиске: большая часть работы уже сделана для перехода к текущей позиции, поэтому очень мало нужно делать, чтобы выйти из нее. Единственная небольшая сложность заключается в том, что логика, которая верна в конце строки, ошибочно дает неправильные подстроки в начале. Это требует некоторого кода инициализации.
алгоритм kmp_table : input : массив символов, W (слово для анализа) вывод : массив целых чисел, T (таблица для заполнения) определить переменные : целое число, pos ← 1 (текущая позиция, которую мы вычисляем в T) целое число, cnd ← 0 (отсчитываемый от нуля индекс в W следующего символа текущей подстроки кандидата) пусть T [0] ← -1 в то время как posdo if W [pos] = W [cnd], тогда пусть T [pos] ← T [cnd] иначе пусть T [pos] ← cnd, пока cnd ≥ 0 и W [pos] ≠ W [cnd ] do let cnd ← T [cnd] let pos ← pos + 1, cnd ← cnd + 1 let T [pos] ← cnd (требуется только при поиске всех вхождений слов)
Эффективность алгоритма построения таблиц
Временная (и пространственная) сложность табличного алгоритма равна , где длина W
.
- Внешний цикл:
pos
инициализируется значением 1, условие цикла равноpos < k
, иpos
увеличивается на 1 на каждой итерации цикла. Таким образом, цикл займет итераций.
- Внутренний цикл:
cnd
инициализируется0
и увеличивается максимум на 1 в каждой итерации внешнего цикла.T[cnd]
всегда меньшеcnd
, поэтомуcnd
уменьшается как минимум на 1 в каждой итерации внутреннего цикла; условие внутреннего циклаcnd ≥ 0
. Это означает, что внутренний цикл может выполняться не более чем столько раз, сколько выполнялся внешний цикл - каждое уменьшениеcnd
на 1 во внутреннем цикле должно иметь соответствующее увеличение на 1 во внешнем цикле. Поскольку внешний цикл принимает итераций внутренний цикл может занять не более всего итераций.
Комбинированные, внешняя и внутренняя петли занимают не более итераций. Это соответствуетВременная сложность использования обозначения Big O .
Эффективность алгоритма KMP
Поскольку две части алгоритма имеют сложность соответственно O(k)
и O(n)
, сложность всего алгоритма составляет O(n + k)
.
Эти сложности одинаковы, независимо от того, сколько повторяющихся паттернов содержится в W
или S
.
Варианты
В режиме реального время версия KMP может быть реализована с помощью отдельной функции сбоя таблицы для каждого символа в алфавите. Если есть несоответствие по характеру в тексте таблица функций отказа для символа консультируется по индексу в шаблоне, в котором имело место несовпадение. Это вернет длину самой длинной подстроки, заканчивающейся на соответствие префиксу шаблона, с добавленным условием, что символ после префикса . С этим ограничением персонажв тексте нет необходимости снова проверять на следующем этапе, и поэтому между обработкой каждого индекса текста выполняется только постоянное количество операций [ необходима ссылка ] . Это удовлетворяет ограничению вычислений в реальном времени.
В алгоритме Бута использует модифицированную версию функции предварительной обработки KMP , чтобы найти лексикографический минимальное вращение строки . Функция разрушения постепенно вычисляется по мере вращения струны.
Заметки
- ^ m - длина шаблона, то есть строка, которую мы ищем в тексте длиной n.
Рекомендации
- ^ a b Кнут, Дональд; Моррис, Джеймс Х .; Пратт, Воан (1977). «Быстрое сопоставление с образцом в строках». SIAM Journal on Computing . 6 (2): 323–350. CiteSeerX 10.1.1.93.8147 . DOI : 10.1137 / 0206024 .
- ^ Кнут, Дональд Э. (1973). «Опасности теории информатики». Исследования по логике и основам математики . 74 : 189–195. DOI : 10.1016 / S0049-237X (09) 70357-X . ISBN 9780444104915.
- ^ Моррис, JH, младший; Пратт, В. (1970). Алгоритм линейного сопоставления с образцом (Технический отчет). Калифорнийский университет, Беркли, вычислительный центр. TR-40.
- ^ Матиясевич, Юрий (1971). "О распознавании в реальное время отношения вхождения" (PDF) . Записки научных семинаров Ленинградского отделения Математического института им. В.А.Стеклова . 20 : 104–114., переводится на английский как Матиясевич, Юрий (1973). «Распознавание отношения включения в реальном времени» . Журнал советской математики . 1 : 64–70. DOI : 10.1007 / BF01117471 .
- ^ Кнут упоминает об этом факте в своей книге Избранные статьи по разработке алгоритмов :
В 2012 году я узнал, что Юрий Матиясевич предвидел описанные в этой статье алгоритмы сопоставления с образцом в линейном времени и алгоритмы предварительной обработки образцов в частном случае двоичного алфавита еще в 1969 году. Он представил их как конструкции для машины Тьюринга с двумерным рабочая память.
- ^ Амир, дружба; Landau, Gad M .; Левенштейн, Моше; Сокол, Дина (2007). «Сопоставление динамического текста и статического шаблона». ACM Trans. Алгоритмы . 3 (2): 19. DOI : 10,1145 / 1240233,1240242 .
- Кормен, Томас ; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001). «Раздел 32.4: Алгоритм Кнута-Морриса-Пратта». Введение в алгоритмы (второе изд.). MIT Press и McGraw-Hill. стр. 923 -931. ISBN 0-262-03293-7. Zbl 1047.68161 .
- Крошмор, Максим; Риттер, Войцех (2003). Жемчужины стрингологии. Текстовые алгоритмы . Ривер Эдж, Нью-Джерси: World Scientific. С. 20–25. ISBN 981-02-4897-0. Zbl 1078.68151 .
- Шпанковский, Войцех (2001). Анализ среднего случая алгоритмов на последовательностях . Серия Wiley-Interscience по дискретной математике и оптимизации. С предисловием Филиппа Флажоле. Чичестер: Вайли. С. 15–17, 136–141. ISBN 0-471-24063-X. Zbl 0968.68205 .
Внешние ссылки
- Анимация апплета поиска строки
- Объяснение алгоритма и образец кода С ++ по Дэвиду Eppstein
- Описание алгоритма Кнута-Морриса-Пратта и код C Кристианом Чаррасом и Тьерри Лекроком
- Разъяснение алгоритма с нуля Фленсбургом.
- Чу-Ченг Се, разоблачающие этапы запуска КМП
- Видео лекции НПТЕЛГРД на YouTube
- Видео лекции LogicFirst на YouTube
- Доказательство правильности
- Преобразование между различными формами алгоритма
- Алгоритм Кнута-Морриса-Пратта, написанный на C #