Z-функция
| Определение: |
| Z-функция (англ. Z-function) от строки и позиции — это длина максимального префикса подстроки, начинающейся с позиции в строке , который одновременно является и префиксом всей строки . Более формально, . Значение Z-функции от первой позиции не определено, поэтому его обычно приравнивают к нулю или к длине строки. |
Примечание: далее в конспекте символы строки нумеруются с нуля.
Тривиальный алгоритм
Простая реализация за , где — длина строки. Для каждой позиции перебираем для неё ответ, начиная с нуля, пока не обнаружим несовпадение или не дойдем до конца строки.
Псевдокод
int[] zFunction(s : string):
int[] zf = int[n]
for i = 1 to n − 1
while i + zf[i] < n and s[zf[i]] == s[i + zf[i]]
zf[i]++
return zf
Эффективный алгоритм поиска
Z-блоком назовем подстроку с началом в позиции и длиной .
Для работы алгоритма заведём две переменные: и — начало и конец Z-блока строки с максимальной позицией конца (среди всех таких Z-блоков, если их несколько, выбирается наибольший). Изначально и .
Пусть нам известны значения Z-функции от до . Найдём .
Рассмотрим два случая.
- :
Просто пробегаемся по строке и сравниваем символы на позициях и .Пусть первая позиция в строке для которой не выполняется равенство , тогда это и Z-функция для позиции . Тогда . В данном случае будет определено корректное значение в силу того, что оно определяется наивно, путем сравнения с начальными символами строки. - :
Сравним и . Если меньше, то надо просто наивно пробежаться по строке начиная с позиции и вычислить значение . Корректность в таком случае также гарантирована.Иначе мы уже знаем верное значение , так как оно равно значению .
Время работы
Этот алгоритм работает за , так как каждая позиция пробегается не более двух раз: при попадании в диапазон от до и при высчитывании Z-функции простым циклом.
Псевдокод
int[] zFunction(s : string):
int[] zf = int[n]
int left = 0, right = 0
for i = 1 to n − 1
zf[i] = max(0, min(right − i, zf[i − left]))
while i + zf[i] < n and s[zf[i]] == s[i + zf[i]]
zf[i]++
if i + zf[i] >= right
left = i
right = i + zf[i]
return zf
Поиск подстроки в строке с помощью Z-функции
— длина текста. — длина образца.
Образуем строку s = pattern + # + text, где # — символ, не встречающийся ни в text, ни в pattern. Вычисляем Z-функцию от этой строки.
В полученном массиве, в позициях в которых значение Z-функции равно , по определению начинается подстрока, совпадающая с pattern.
Псевдокод
int substringSearch(text : string, pattern : string):
int[] zf = zFunction(pattern + '#' + text)
for i = m + 1 to n + 1
if zf[i] == m
return i
