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 случая: \begin{enumerate} \item '"`UNIQ-MathJax24-QINU`"'. В этом случае '"`UNIQ-MathJax25-QINU`"' мы пересчитываем вручную по определению, заодно обновляя '"`UNIQ-MathJax26-QINU`"' и '"`UNIQ-MathJax27-QINU`"'. \item '"`UNIQ-MathJax28-QINU`"'. В этом случае мы знаем, что '"`UNIQ-MathJax29-QINU`"' `локально` наше положение в строке `похоже` на то, что происходило, когда мы считали '"`UNIQ-MathJax30-QINU`"'. Далее идёт 2 случая: \begin{enumerate} \item '"`UNIQ-MathJax31-QINU`"'. В этом случае мы можем сразу сказать, что '"`UNIQ-MathJax32-QINU`"', поскольку '"`UNIQ-MathJax33-QINU`"'-блок такой длины в '"`UNIQ-MathJax34-QINU`"' точно есть, а если бы он был больше, чем '"`UNIQ-MathJax35-QINU`"', то это бы означало, что '"`UNIQ-MathJax36-QINU`"' посчитана неправильно (а мы, разумеется, считаем всё правильно, потому что мы молодцы). \item '"`UNIQ-MathJax37-QINU`"'. В этом случае мы знаем, что '"`UNIQ-MathJax38-QINU`"' как минимум равняется '"`UNIQ-MathJax39-QINU`"', но она может быть и больше. Раз она может быть больше, то мы проверим это, заодно сдвинув '"`UNIQ-MathJax40-QINU`"' (если '"`UNIQ-MathJax41-QINU`"'-блок получится увеличить). Если же увеличить не удалось, то нам всё равно хорошо, поскольку мы посчитали ответ за '"`UNIQ-MathJax42-QINU`"'. \end{enumerate}

\end{enumerate}

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

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