Как работают алгоритм Кнута-Морриса-Пратта и префикс-функция?

Префикс-функция для позиции i — длина наибольшего собственного префикса строки, совпадающего с суффиксом, оканчивающимся в i; КМП использует её, чтобы искать подстроку за O(n + m) без откатов по тексту.

Идея алгоритма

При несовпадении наивный поиск возвращается в начало паттерна и пересравнивает символы. КМП знает из префикс-функции, какой префикс паттерна уже совпал с хвостом прочитанного текста, и продолжает с него — указатель по тексту никогда не идёт назад.

Построение префикс-функции

Вычисляется за O(m) тем же приёмом: пробуем продлить предыдущее совпадение, при неудаче «проваливаемся» по уже посчитанным значениям функции.

s = a b a b a
p = 0 0 1 2 3

Сложность и применения

• Время O(n + m), память O(m) против O(n·m) наивного перебора.
• Поиск подстроки, период строки, подсчёт вхождений каждого префикса.

Коротко для собеседования

КМП заранее считает для паттерна префикс-функцию и при несовпадении сдвигает паттерн, не возвращаясь назад по тексту, — отсюда O(n + m). Пригодится для поиска подстроки и периода строки; Z-функция решает те же задачи другим способом.