Алгоритмы строк: KMP, Z-функция, суффиксный массив

Строковые алгоритмы — база для поиска подстрок, анализа текста, автодополнения, биоинформатики и задач на соревнованиях. Если коротко: KMP и Z-функция помогают искать шаблон в строке за линейное время, а суффиксный массив — мощный инструмент для сложных запросов по тексту.

• KMP (Knuth–Morris–Pratt)
  Решает задачу поиска подстроки pattern в строке text за O(n + m).
  Главная идея — не возвращаться назад по тексту, если уже известно, какая часть шаблона совпала.
• Используется префикс-функция: для каждой позиции хранится длина наибольшего собственного префикса, который одновременно является суффиксом.
• Почему это полезно:
  • быстрый поиск без лишних сравнений
  • хорошо работает на длинных строках
  • часто встречается в интервью и задачах по алгоритмам
• Подходит, когда нужен поиск всех вхождений шаблона в тексте.
• Z-функция
  Для каждой позиции показывает, какова длина наибольшего префикса строки, совпадающего с подстрокой, начинающейся в этой позиции. Считается за O(n).
  Где полезна:
  • поиск подстроки через строку вида pattern#text
  • поиск повторов и периодов строки
  • анализ схожести префикса с другими частями строки
  На практике Z-функция нередко проще для понимания в задачах на “совпадения с префиксом”, чем KMP. 🧠
• Суффиксный массив
  Это массив индексов всех суффиксов строки, отсортированных лексикографически.
  Пример: для строки banana суффиксы сортируются как a, ana, anana, banana, na, nana.
• Что дает суффиксный массив:
  • поиск подстроки за O(m log n) через бинарный поиск
  • поиск количества различных подстрок
  • нахождение LCP — длины общего префикса соседних суффиксов
  • решение задач на повторяющиеся подстроки, общие подстроки и сжатие текста
• По сравнению с KMP и Z-функцией, это уже инструмент не для одного шаблона, а для множества запросов к одной строке. ⚙️
• Что выбрать на практике
  • KMP — когда нужно искать конкретный шаблон в тексте
  • Z-функция — когда задача связана с префиксами, периодами, совпадениями
  • Суффиксный массив — когда нужен продвинутый анализ строки и много запросов
• Короткое сравнение
  • KMP: поиск шаблона, O(n + m)
  • Z-функция: анализ структуры строки, O(n)
  • Суффиксный массив: мощная индексация строки, обычно построение от O(n log n)
• Итог:
  KMP и Z-функция — обязательный минимум для работы со строками.
  Суффиксный массив — следующий уровень, если нужно решать сложные задачи поиска и анализа текста. 🚀
• Подборку каналов про IT стоит сохранить отдельно — там удобно следить за алгоритмами, backend, data structures и практике разработки 📚

🗣 Подборки каналов
🧠 Каталог ботов и приложений
🗺 Навигация