Префиксная функция KMP
Находите шаблон за O(n + m)
«Префиксная функция KMP» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
Задача поиска шаблона
Вам нужно найти, где небольшой шаблон встречается в большом тексте. Наивные проверки медленны, поэтому на соревнованиях полезен более умный способ сканирования. 🔍
Почему наивный поиск медленный
Сравнение шаблона на каждой позиции может занимать O(n*m) времени. На больших входных данных это незаметно приводит к превышению ограничения по времени.
Познакомьтесь с префиксной функцией
Префиксная функция в каждой позиции определяет длину самого длинного собственного префикса, который одновременно является суффиксом. Это основа KMP.
Собственный префикс и суффикс
Собственный префикс или суффикс не совпадает со всей строкой целиком. Для ababa самая длинная совпадающая пара имеет длину 3: aba.
Что хранит pi[i]
Мы сохраняем значения в массиве с именем pi. Здесь pi[i] — длина самого длинного совпадения префикса и суффикса для фрагмента, заканчивающегося в позиции i.
Построение pi за один проход
Вы строите pi слева направо, повторно используя предыдущие значения вместо новой проверки с начала. В этом повторном использовании и заключается весь приём.
def prefix_function(s):
pi = [0] * len(s)
return piЦикл отката
При несовпадении символов выполняйте откат к pi[k-1], а не сбрасывайте значение в ноль. Это позволяет не повторять уже выполненную работу.
while k > 0 and s[i] != s[k]:
k = pi[k - 1]Продлите совпадение
Если текущие символы совпадают, увеличьте длину на единицу и запишите её. Несовпадение при нулевой длине просто оставляет значение равным нулю.
if s[i] == s[k]:
k += 1
pi[i] = kПоиск с помощью этого приёма
Чтобы найти шаблон в тексте, объедините их как pattern + sep + text. Любое значение pi, равное длине шаблона, означает полное совпадение.
combined = pattern + chr(0) + text
pi = prefix_function(combined)Зачем нужен разделитель
Разделитель — это символ, отсутствующий в обеих строках. Он не даёт совпадениям пересекать границу объединения и порождать ложные результаты.
Преимущество линейного времени
И построение, и поиск выполняются за O(n + m). Каждый символ обрабатывается один раз, поэтому KMP подходит для огромных входных данных на соревнованиях.
Быстрая проверка
Проверьте, насколько хорошо вы поняли, что записывает префиксная функция.
Итоги: KMP вкратце
Вы изучили префиксную функцию: один раз постройте pi, при несовпадениях выполняйте откат и ищите за линейное время. Это KMP в двух словах. 🎯
Часто задаваемые вопросы
Урок «Префиксная функция KMP» бесплатный?
Да — полный текст урока «Префиксная функция KMP» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «Префиксная функция KMP»?
Находите шаблон за O(n + m) Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.
Сколько времени занимает урок «Префиксная функция KMP»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Префиксная функция KMP
- Полиномиальное хеширование строк
- Z-функция для поиска шаблона
- Деревья поиска по префиксам