Алгоритм Кнута — Морриса — Пратта (КМП-алгоритм), алгоритм поиска образца (подстроки) в строке.

Алгоритм был открыт Д. Кнутом и В. Праттом и, независимо от них, Д. Моррисом. Результаты своей работы они опубликовали совместно в 1977 году.

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

Рассмотрим сравнение строк на позиции , где образец  сопоставляется с частью текста . Предположим, что первое несовпадение произошло между  и , где . Тогда  и .

При сдвиге вполне можно ожидать, что префикс (начальные символы) образца  сойдется с каким-нибудь суффиксом (конечные символы) текста . Длина наиболее длинного префикса, являющегося одновременно суффиксом, есть префикс-функция от строки  для индекса .

Это приводит нас к следующему алгоритму: пусть  — префикс-функция от строки  для индекса . Тогда после сдвига мы можем возобновить сравнения с места  и  без потери возможного местонахождения образца. Средствами амортизационного анализа можно показать, что таблица  может быть вычислена за  сравнений перед началом поиска. А поскольку строка  будет пройдена ровно один раз, суммарное время работы алгоритма будет равно , где n - длина текста .