KMP

Info

Функция Кнута-Морриса-Пратта (KMP) - это алгоритм поиска подстроки в строке, который работает за линейное время O(n), где n - длина текста. Он использует префикс-функцию, которая позволяет избежать линейного сканирования текста для каждой позиции в нем.

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

Основная идея алгоритма KMP заключается в том, что мы не просто сдвигаемся по тексту, если мы обнаружили несовпадение, а сдвигаемся на основании информации, предоставленной префикс-функцией. Это позволяет избежать повторных сравнений символов, которые мы уже сравнили.