Алгоритм Кнута — Морриса — Пратта (КМП-алгоритм) используется для поиска подстроки в строке. 5 Он основывается на том, что после частичного совпадения начальной части подстроки с соответствующими символами строки становится известна пройденная часть строки. 5 Это позволяет вычислить некоторые сведения, с помощью которых затем быстро продвинуться по строке. 5

Идея алгоритма состоит в том, чтобы не прикладывать подстроку к строке со сдвигом всего в один символ, а максимально увеличить это расстояние, сократив таким образом количество сравнений. 4

Алгоритм работает за линейное время от длины обеих строк. 3 Он находит все вхождения образца в строку и особенно эффективен на больших текстах или слабых процессорах. 2