Алгоритмы
Z-функция: Эффективный поиск подстрок
Цели урока
- Понять определение и смысл Z-функции
- Разобраться в концепции Z-box и трёх случаях алгоритма
- Реализовать линейный O(n) алгоритм вычисления
- Применять Z-функцию для поиска подстрок
- Решать задачи о периодах и границах строк
Предварительные знания
- Понимание строк и подстрок
- Алгоритм KMP (желательно для сравнения)
- Базовое понимание амортизированного анализа
Как найти слово в книге за линейное время?
- Z-функция: must-have для строковых задач на олимпиадах и собеседованиях
- Биоинформатика: поиск генов в ДНК последовательностях
- Компиляторы: лексический анализ исходного кода
- Сжатие данных: поиск повторяющихся паттернов (LZ77, LZ78)
Z-алгоритм и спортивное программирование
Z-функция вычисляет для каждой позиции строки длину наибольшего совпадения с её началом и позволяет за линейное время решать задачу поиска подстроки. Идею популяризировал Дэн Гасфилд в книге 1997 года 'Algorithms on Strings, Trees, and Sequences', где аккуратно разобрал линейные методы работы со строками. В отличие от более раннего алгоритма Кнута-Морриса-Пратта, Z-функция концептуально проще и потому стала любимым инструментом в спортивном программировании, через которое и получила широкую известность.
Зачем нужна Z-функция?
Задача поиска подстроки (pattern matching) - одна из древнейших в computer science. Нужно найти все вхождения шаблона P в тексте T. Наивный алгоритм работает за O(|P| × |T|) - слишком медленно для больших текстов.
**Метафора: поиск в библиотеке**
Представь, что ты ищешь конкретную фразу в огромной книге. Наивный способ - читать посимвольно, и при несовпадении начинать заново со следующей позиции. Но если ты уже прочитал "ABABAB" и ищешь "ABAC", зачем начинать с нуля? Ты уже знаешь, что следующий возможный match начинается с позиции 2 ("ABAB")!
Z-функция (как и KMP) решает эту проблему за O(|T| + |P|). Ключевая идея: использовать уже вычисленную информацию о совпадениях.
Z-функция - альтернатива KMP, часто более интуитивная. Вместо "prefix function" (какой суффикс совпадает с префиксом), Z-функция напрямую отвечает на вопрос: **насколько длинный префикс строки совпадает с подстрокой, начинающейся в позиции i?**
Почему наивный поиск подстроки работает за O(n × m)?
Для каждой из (n-m+1) стартовых позиций может потребоваться до m сравнений. В худшем случае это O((n-m) × m) ≈ O(n × m).
Определение Z-функции
**Z-функция** строки s - это массив z[], где **z[i] = длина наибольшего общего префикса** строки s и подстроки s[i:].
Проще говоря: z[i] отвечает на вопрос "Начиная с позиции i, сколько символов подряд совпадают с началом строки?"
Визуализация: каждое z[i] показывает, какой «кусок» начала строки «повторяется» в позиции i.
**Наивный алгоритм** вычисления Z-функции: для каждой позиции i просто сравниваем символы.
Z-функция тесно связана с понятием 'Z-box' - отрезком, где подстрока совпадает с префиксом. Это ключ к линейному алгоритму!
Чему равна z[4] для строки s = "ababab"?
s[4:] = "ab". Сравниваем с s = "ababab": a=a ✓, b=b ✓, но s[4:] заканчивается. z[4] = 2.
Линейный алгоритм: Z-box
Наивный алгоритм O(n²) - слишком медленный. Но мы можем использовать уже вычисленные значения z[], чтобы избежать повторных сравнений!
**Ключевая идея: Z-box**
Z-box - это отрезок [l, r], где r - **самая правая позиция**, достигнутая при предыдущих вычислениях, такая что s[l:r] = s[0:r-l]. Другими словами, мы помним «самое правое» совпадение с префиксом.
**Три случая при вычислении z[i]:**
Полный линейный алгоритм:
**Почему это O(n)?**
**Пошаговый пример:**
Красота алгоритма: мы никогда не сравниваем один и тот же символ дважды! Либо используем готовый результат, либо расширяем r вправо.
Почему в линейном алгоритме мы берём min(r-i, z[i-l])?
z[i-l] показывает совпадение с позиции (i-l) в префиксе. Но мы знаем, что Z-box (совпадение с i) гарантировано только до r. Если z[i-l] выходит за r-i, нужно проверять дальше вручную.
Применения Z-функции
Z-функция - мощный инструмент для множества строковых задач. Главное применение - **поиск подстроки за O(n+m)**.
**Применение 1: Поиск pattern в text**
Идея: склеиваем pattern + '$' + text (где '$' - разделитель, отсутствующий в обеих строках). Вычисляем Z-функцию. Если z[i] = |pattern|, значит в этой позиции (в части text) начинается вхождение!
**Применение 2: Минимальный период строки**
**Применение 3: Поиск всех border (границ) строки**
**Сравнение Z-функции и KMP:**
На собеседованиях и олимпиадах Z-функция часто предпочтительнее KMP из-за более простой реализации. Но для потокового поиска (когда текст приходит по частям) KMP удобнее.
Как искать pattern в text с помощью Z-функции?
Конкатенируем pattern$text ($ - разделитель). Вычисляем Z-функцию. Если z[i] = len(pattern), значит в позиции i начинается полное совпадение с pattern (в части text).
Итоги
- Z[i] = длина наибольшего общего префикса строки s и подстроки s[i:]
- Линейный алгоритм использует Z-box: самый правый отрезок с известным совпадением
- Если i внутри Z-box, можем переиспользовать z[i-l]
- Применения: поиск подстроки O(n+m), минимальный период, границы (borders) строки
- Z-функция эквивалентна KMP prefix function и конвертируется в неё
Связь с другими строковыми алгоритмами
Z-функция математически эквивалентна prefix-функции KMP и может быть конвертирована в неё за O(n).
- KMP (Кнут-Моррис-Пратт) — Эквивалентный алгоритм с prefix-функцией
- Суффиксные массивы — Более мощная структура для строковых задач
- Алгоритмы сжатия (LZ77, LZ78) — Используют Z-функцию для поиска повторов
Связанные уроки
- alg-24-kmp — Z-функция и префикс-функция KMP решают одну задачу линейно
- alg-23-pattern-matching — Z-функция - линейный ответ на поиск подстроки
- alg-38-radix-sort — Поразрядная сортировка суффиксов помогает строить суффиксные массивы
- dm-15 — Z-массив кодирует структуру самоналожения строки
- nlp-01