Z-функция: различия между версиями
Строка 24: | Строка 24: | ||
На каждом шаге алгоритма (которых $n$) мы совершаем $O(1)$ действий, связанных с проверкой разных условий $+$ какое-то количество действий, связанных со сравнением символов. Однако каждый раз, когда нам надо делать сравнение пары символов, мы сдвигаем на единицу $R ~-$ правую границу нашего самого правого $z$-блока. Поскольку сдвинуть её мы сможем не больше, чем на $O(n)$, то и суммарная сложность алгоритма составляет $O(n)$. | На каждом шаге алгоритма (которых $n$) мы совершаем $O(1)$ действий, связанных с проверкой разных условий $+$ какое-то количество действий, связанных со сравнением символов. Однако каждый раз, когда нам надо делать сравнение пары символов, мы сдвигаем на единицу $R ~-$ правую границу нашего самого правого $z$-блока. Поскольку сдвинуть её мы сможем не больше, чем на $O(n)$, то и суммарная сложность алгоритма составляет $O(n)$. | ||
+ | |||
+ | {{Автор|Александр Гришутин|rationalex}} |
Версия 23:12, 22 марта 2020
Содержание
Определение
Назовём $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 случая:
- $i \geq R$. В этом случае $z[i]$ мы пересчитываем вручную по определению, заодно обновляя $L$ и $R$.
- $L < i \leq R$. В этом случае мы знаем, что $s[L:R] = s[0:(R-L)] \implies$ "локально" наше положение в строке "похоже" на то, что происходило, когда мы считали $z[i-L]$. Далее идёт 2 случая:
- $i + z[i - L] < R$. В этом случае мы можем сразу сказать, что $z[i] = z[i - L]$, поскольку $z$-блок такой длины в $i$ точно есть, а если бы он был больше, чем $z[i - L]$, то это бы означало, что $z[i - L]$ посчитана неправильно (а мы, разумеется, считаем всё правильно, потому что мы молодцы).
- $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