Z-функция

Определение

Назовём $z$-блоком строки $s$ такую её подстроку $s[i:i+len]$, что $s[i:i+len] = s[0:len]$.

Постановка задачи

Для данной строки $s$ длины $n$ посчитать массив значений $z$-функции $z[i]_{i \in [0:n-1]}$, где $z[i] ~-$ наибольшего $z$-блока, начинающегося в $i$ позиции.

Наивное решение

Очевидно, что можно посчитать все значения $z$-функции за $O(n^2)$, отдельно считая её для каждой позиции в строке. Однако этот подход неоптимален, поскольку не использует информацию, полученную на предыдущих шагах.

Решение за $O(n)$

Будем считать значения $z$-функции по возрастанию индекса в строке, при этом храня самый правый (с наибольшей правой границей) $z$-блок (назовём его границы $L$ и $R$, где $L$ мы включаем, а $R ~-$ нет), найденный нами по ходу построения массива $z$-функции.

При подсчёте $z[i]$ возможны 3 случая:

1. $i \geq R$. В этом случае $z[i]$ мы пересчитываем вручную по определению, заодно обновляя $L$ и $R$.
2. $L < i \leq R$. В этом случае мы знаем, что $s[L:R] = s[0:(R-L)] \implies$ "локально" наше положение в строке "похоже" на то, что происходило, когда мы считали $z[i-L]$. Далее идёт 2 случая:
   1. $i + z[i - L] < R$. В этом случае мы можем сразу сказать, что $z[i] = z[i - L]$, поскольку $z$-блок такой длины в $i$ точно есть, а если бы он был больше, чем $z[i - L]$, то это бы означало, что $z[i - L]$ посчитана неправильно (а мы, разумеется, считаем всё правильно, потому что мы молодцы).
   2. $i + z[i-L] \geq R$. В этом случае мы знаем, что $z[i]$ как минимум равняется $R-i$, но она может быть и больше. Раз она может быть больше, то мы проверим это, заодно сдвинув $R$ (если $z$-блок получится увеличить). Если же увеличить не удалось, то нам всё равно хорошо, поскольку мы посчитали ответ за $O(1)$.

Оценка сложности

На каждом шаге алгоритма (которых $n$) мы совершаем $O(1)$ действий, связанных с проверкой разных условий $+$ какое-то количество действий, связанных со сравнением символов. Однако каждый раз, когда нам надо делать сравнение пары символов, мы сдвигаем на единицу $R ~-$ правую границу нашего самого правого $z$-блока. Поскольку сдвинуть её мы сможем не больше, чем на $O(n)$, то и суммарная сложность алгоритма составляет $O(n)$.

---

Автор конспекта: Александр Гришутин

По всем вопросам пишите в telegram @rationalex