Где применяется
1. Задача
У простого поиска из шага 126 одна слабость. После несовпадения он сдвигает паттерн (образец) на одну позицию вправо и снова сравнивает символы текста, которые уже видел. Из-за этого он стоит O(n·m). KMP (алгоритм Кнута-Морриса-Пратта) устраняет именно это. Он идёт по тексту один раз, слева направо, и никогда не возвращается назад. Для этого ему нужна маленькая таблица. Её строят по одному паттерну ещё до поиска, и она говорит, куда передвинуться в паттерне при несовпадении. Итог O(n + m): линейно по длине текста плюс по длине паттерна.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи про префиксы строки, которые одновременно её суффиксы, и поиск, который должен уложиться в O(n + m) на длинных строках. Таблица LPS отвечает на оба вопроса, а поиск никогда не двигается по тексту назад.
Это search из урока, остановленный на первом совпадении. Он работает за O(n + m) на любых данных.
Последнее значение таблицы LPS это длина самого длинного счастливого префикса, так что построй таблицу и отрежь.
Если L это последнее значение LPS, то s состоит из одного повторённого куска ровно тогда, когда L больше 0 и n делится на n минус L.
Построй LPS для s, разделителя и перевёрнутой s. Последнее значение это самый длинный палиндром в начале s, а остаток отражается и ставится спереди.