Объясните принцип работы алгоритма поиска подстроки Кнута-Морриса-Пратта.

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

Основная идея — предварительно вычислить для подстроки массив префикс-функций (или "π-массив"), который показывает, сколько символов совпало с началом подстроки при неудачном сравнении. Это позволяет при несовпадении не возвращаться назад в исходной строке, а сдвигать подстроку на оптимальное количество позиций.

Пример:

• Есть текст: "ABABDABACDABABCABAB"
• Ищем подстроку: "ABABCABAB"

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

Это обеспечивает сложность O(n + m), где n — длина текста, m — длина подстроки, что эффективнее наивного поиска.