Z-функция строки за O(n): построение и применение

Z-функция - компактная характеристика строки, на которой строится едва ли не половина олимпиадного арсенала по работе с текстами: поиск подстроки, подсчёт различных подстрок, определение периодов. Идея простая: для каждой позиции $i$ хранится длина наибольшего префикса исходной строки, который начинается именно отсюда. Полный массив строится за $O(n)$ с одним указателем «правого края уже изученной области».

Определение $z[i]$ через максимальный префикс

Пусть $s$ - строка длины $n$, индексация с нуля. Z-функция - это массив $z$ той же длины, где

$z[i] = \max\{k \ge 0 : s[0..k{-}1] = s[i..i{+}k{-}1]\}.$

Словами: $z[i]$ - длина наибольшего префикса $s$, совпадающего с подстрокой, начинающейся в позиции $i$. По соглашению $z[0]$ либо не определяется, либо полагается равным $n$ (вся строка - префикс самой себя) - на алгоритм это никак не влияет, главное - не использовать $z[0]$ в применениях.

Простой пример: для $s = \text{aabcaab}$

$z[4] = 3$, потому что с позиции 4 идёт $\text{aab}$ - это первые 3 символа $s$. $z[1] = 1$: совпадает только $\text{a}$, дальше второй символ $s$ - это $\text{a}$, а $s[2] = \text{b}$. Всё остальное - нули, потому что соответствующие символы не равны $s[0]$.

Отличие от префикс-функции

Z-функция и префикс-функция $\pi$ из алгоритма Кнута-Морриса-Пратта родственны, но смотрят на строку с разных концов. $\pi[i]$ - длина наибольшего собственного префикса подстроки $s[0..i]$, который одновременно является её суффиксом: фокус на отрезке от 0 до $i$, и совпадение проверяется в конце. $z[i]$ - фокус на позиции $i$ и проверяется, как далеко вперёд тянется совпадение с префиксом всей строки.

Формально обе функции взаимовыразимы за $O(n)$: по $\pi$ можно восстановить $z$ и наоборот. На практике Z-функция чаще проще в реализации (меньше тонких case'ов с while-циклом по $\pi$), а $\pi$ удобнее, когда нужны именно «откаты» в KMP-стиле. Многие задачи решаются обеими - выбор сводится к привычке.

Наивный $O(n^2)$ и идея ускорения

Наивный алгоритм - посимвольно сравнивать $s[0..]$ и $s[i..]$, пока совпадает. Худший случай - строка из одинаковых символов $\text{aaaa...a}$: каждое $z[i] = n - i$, суммарно $\Theta(n^2)$ операций.

Ускорение опирается на наблюдение: если мы уже посчитали $z[j]$ для $j < i$ и знаем самый правый «Z-блок» $[l, r]$, где $r = l + z[l] - 1$ - конец совпавшего префикса, - то значения внутри блока можно частично восстановить без сравнений символов. Подстрока $s[l..r]$ совпадает с $s[0..r-l]$, и любую позицию $i$ внутри $[l, r]$ можно сопоставить с зеркальной $i - l$ в начале строки и использовать $z[i - l]$ как нижнюю оценку.

Алгоритм по шагам с двумя случаями

Поддерживаем пару $(l, r)$ - самый правый Z-блок, изначально $l = r = 0$. Для каждого $i$ от 1 до $n - 1$:

Случай 1: $i > r$. Z-блок нас не покрывает, ничего полезного из прошлого не вытащить - стартуем «голое» сравнение $s[0..]$ и $s[i..]$ с нуля и увеличиваем $z[i]$, пока символы совпадают. После - обновляем $l = i$, $r = i + z[i] - 1$, если $z[i] > 0$.

Случай 2: $i \le r$. Внутри блока. Зеркало $j = i - l$, и мы знаем $z[j]$. Возможны две ветки:

• $z[j] < r - i + 1$ - зеркальное значение меньше, чем расстояние до правой границы. Тогда $z[i] = z[j]$ железно: дальше тянуть нельзя, потому что в зеркальной позиции совпадение уже оборвалось, а у нас та же подстрока.
• $z[j] \ge r - i + 1$ - зеркало упирается в границу, и за неё мы не знаем, что там. Берём нижнюю оценку $z[i] = r - i + 1$ и пытаемся «дотянуть» сравнением символов начиная с позиции $r + 1$. Если получилось - обновляем $r$ (и $l = i$).

Псевдокод:

l = r = 0
for i in 1..n-1:
    if i <= r:
        z[i] = min(r - i + 1, z[i - l])
    while i + z[i] < n and s[z[i]] == s[i + z[i]]:
        z[i] += 1
    if i + z[i] - 1 > r:
        l = i
        r = i + z[i] - 1

Шесть строк - весь алгоритм. Никаких массивов алфавита, никаких отдельных билдеров.

Сложность $O(n)$ через амортизированный анализ

Внешний цикл - $n$ итераций. Сравнения символов делаются только в while, и каждое успешное сравнение увеличивает $r$ как минимум на единицу. Указатель $r$ монотонно растёт и не превосходит $n - 1$ - всего успешных сравнений не больше $n$. Неуспешных - тоже не больше $n$: по одному на итерацию внешнего цикла. Итого все сравнения суммарно $O(n)$, плюс $n$ административных операций - $O(n)$ времени и $O(n)$ памяти под массив. Анализ почти дословно повторяет KMP: «работа равна суммарному движению одного указателя».

Применения

**Поиск подстроки $P$ в $T$ через P\T$.** Берём$s = P + $ + T$, где$$$- символ, не встречающийся ни в$P$, ни в$T$. Считаем$z$на$s$. Каждая позиция$i$в части$T$, где$z[i] = |P|$, - начало вхождения. Время$O(|P| + |T|)$ - функционально эквивалентно KMP, реализация короче.

Число различных подстрок. Добавляя по одному символу в конец строки $s$ длины $k$, считаем Z-функцию для развёрнутой $s'$ длины $k + 1$ - новых подстрок добавляется $k + 1 - \max z[i]$. Просуммировав, получаем ответ за $O(n^2)$. Не самый быстрый способ (суффиксный массив даёт $O(n \log n)$), но самый простой.

Периоды строки. $k$ - период $s$, если $s[i] = s[i + k]$ для всех $i$. Эквивалентно: $z[k] \ge n - k$. Перебрав все $k$, за линейное время находим все периоды.

Палиндромы через комбинацию с Манакером. Z-функция для $s + \# + \text{reverse}(s)$ даёт палиндромные префиксы. Сам алгоритм Манакера работает быстрее, но в задачах с дополнительными ограничениями такой гибрид иногда удобнее.

Сравнение с KMP

Z-функция и префикс-функция $\pi$ - две стороны одной медали. Из $\pi$ строится $z$ за $O(n)$ и наоборот. Обе работают за линию, обе используют амортизированный анализ через один монотонный указатель.

Различия - в форме изложения. $z[i]$ описывает «что начинается в позиции $i$»; $\pi[i]$ - «что заканчивается в $s[0..i]$». Олимпиадные шаблоны чаще берут Z - за десяток строк кода и однозначную интерпретацию. KMP остаётся стандартом в учебниках и в реализациях String.indexOf.

Типовые задачи (Codeforces)

• CF 126B Password. Самый длинный префикс, который встречается ещё как минимум один раз и в середине, и в конце. Префикс длины $k$ - суффикс, если $z[n-k] = k$; встречается в середине - если $\max_{1 \le i < n-k} z[i] \ge k$.
• CF 432D Prefixes and Suffixes. Все префиксы строки, которые одновременно являются суффиксами, и число вхождений каждого. Z-функция даёт это в одну итерацию.
• CF 119D String Transformation. Минимальная циклическая ротация - через Z или Booth, обе линейные.

Частые ошибки

• Используют $z[0]$ как полноценное значение. $z[0] = n$ по соглашению, но в большинстве задач его явно исключают: «префикс совпадает сам с собой» - тривиальный факт, не несущий информации.
• **Забывают про разделитель \$$ при поиске P$в$T$.** Без него Z-функция может «протянуть» совпадение из$P$в$T$и дать ложное значение$z[i] > |P|$ - потом непонятно, что считать вхождением.
• Сравнивают $z[i - l]$ с $r - i$ вместо $r - i + 1$. Off-by-one: блок $[l, r]$ включает обе границы, расстояние до конца - $r - i + 1$, а не $r - i$.
• Пытаются обновить $(l, r)$ при $z[i] = 0$. Если ни одного символа не совпало, обновлять блок нельзя - иначе $r$ может уменьшиться.
• Считают, что Z-функция полностью эквивалентна KMP по сложности и поэтому взаимозаменяема в любой задаче. Для одних задач удобнее $z$, для других $\pi$; в задачах с DP по строкам $\pi$ часто даёт более естественные переходы.

FAQ

Что такое Z-функция строки простыми словами? Для каждой позиции $i$ - длина куска, который начинается в $i$ и совпадает с началом строки. Если $s = \text{aabcaab}$, то на позиции 4 строка снова стартует с $\text{aab}$ - те же три первых символа. Значит $z[4] = 3$.

Чем Z-функция отличается от префикс-функции $\pi$? $\pi[i]$ смотрит на подстроку $s[0..i]$ и измеряет, насколько её собственный префикс совпадает с её суффиксом. $z[i]$ фиксирует позицию $i$ и смотрит, как далеко вперёд тянется совпадение с префиксом всей строки. Обе строятся за $O(n)$ и взаимовыразимы.

Как через Z искать подстроку $P$ в тексте $T$? Склеить s = P + \ + T$через разделитель$$$, которого нет ни в одной из строк. Посчитать Z-функцию на$s$. Каждая позиция$i$в части$T$, где$z[i]$равно длине$P$, - начало вхождения. Время - линейное от суммарной длины.

Коротко

Z-функция $z[i]$ - длина наибольшего префикса строки $s$, совпадающего с подстрокой, начинающейся в позиции $i$. Строится за $O(n)$ с одним указателем «правого края» $r$ самого дальнего Z-блока: внутри блока используем уже посчитанное зеркальное значение, вне - стартуем сравнение с нуля. Амортизация - на монотонном росте $r$. Через Z за линейное время решаются поиск подстроки (конкатенация P\T$), подсчёт периодов и числа различных подстрок, проверка границ. С префикс-функцией KMP взаимовыразима - выбор между ними обычно вопрос привычки и читаемости кода.