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
Построение строки по Z-функции
| Задача: |
| Необходимо восстановить строку по Z-функции, считая алфавит ограниченным. |
Описание алгоритма
Пусть в массиве хранятся значения Z-функции, в будет записан ответ. Пойдем по массиву слева направо.
Нужно узнать значение . Для этого посмотрим на значение : если , тогда в запишем ещё не использованный символ или последний использованный символ алфавита, если мы уже использовали все символы. Если , то нам нужно записать префикс длины строки . Но если при посимвольном записывании этого префикса в конец строки мы нашли такой (индекс последнего символа строки), что больше, чем длина оставшейся незаписанной части префикса, то мы перестаём писать этот префикс и пишем префикс длиной строки .
Для правильной работы алгоритма, будем считать значение равным нулю.
Заметим, что не всегда удастся восстановить строку с ограниченным алфавитом неподходящего размера. Например, для строки массив Z-функций будет . Используя двоичный алфавит, мы получим строку , но её массив Z-функций отличается от исходного. Ошибка восстановления строки возникла, когда закончились новые символы алфавита.
Если строить строку по некорректному массиву значений Z-функции, то мы получим какую-то строку, но массив значений Z-функций от неё будет отличаться от исходного.
Реализация
Данный алгоритм работает за .
string buildFromZ(z : int[], alphabet : char[]):
string s = ""
int prefixLength = 0 // длина префикса, который мы записываем
int j // позиция символа в строке, который будем записывать
int newCharacter = 0 // индекс нового символа
for i = 0 to z.length - 1
// мы не пишем какой-то префикс и не будем писать новый
if z[i] = 0 and prefixLength = 0
if newCharacter < alphabet.length
s += alphabet[newCharacter]
newCharacter++
else
s += alphabet[newCharacter - 1]
// нам нужно запомнить, что мы пишем префикс
if z[i] > prefixLength
prefixLength = z[i]
j = 0
// пишем префикс
if prefixLength > 0
s += s[j]
j++
prefixLength--
return s
Доказательство корректности алгоритма
Докажем, что если нам дали корректную Z-функцию, то наш алгоритм построит строку с такой же Z-функцией.
Пусть — данная Z-функция, строку построил наш алгоритм, — массив значений Z-функции для . Покажем, что массивы и будут совпадать.
Рассмотрим похожий алгоритм, но с более худшей асимптотикой. Отличие будет в том, что при мы будем писать префикс полностью и возвращаться в позицию . Рассмотрим каждый шаг этого алгоритма. Если , то мы пишем символ, отличный от первого символа строки, поэтому , а значит . Если , то при записи мы будем получать , потому что мы переписали префикс строки. Но далее мы можем переписать этот префикс другим префиксом. Заметим, что новый префикс будет содержаться и в префиксе самой строки. Поэтому пересечение двух префиксов будет состоять из одинаковых символов. Значит, префикс не будет изменяться, как и значение . Тогда массив совпадает с .
Покажем, что этот алгоритм эквивалентен нашему алгоритму. Когда мы пишем разные префиксы, то возможны три варианта: они не пересекаются, один лежит внутри другого, они пересекаются.
- Если префиксы не пересекаются, то в алгоритме они не влияют друг на друга.
- Если префикс лежит внутри другого префикса, то записав большой префикс мы запишем и малый, поэтому не нужно возвращаться к началу малого префикса.
- Если префиксы пересекаются, то нам нужно переписать часть префикса, который начинается раньше, и начать писать другой префикс (начало этого префикса запишет конец префикса, начинающегося раньше).
Таким образом, алгоритмы эквивалентны и наш алгоритм тоже корректен.
Построение Z-функции по префикс-функции
Постановка задачи
| Задача: |
| Дан массив с корректной префикс-функцией для строки , получить массив с Z-функцией для строки . |
Описание алгоритма
Пусть префикс функция хранится в массиве . Z-функцию будем записывать в массив . Заметим, что если , то мы можем заявить, что будет не меньше, чем .
Так же заметим, что после такого прохода в будет максимальное возможное значение. Далее будем поддерживать инвариант: в будет максимальное возможное значение.
Пусть в , рассмотрю , и . Заметим, что совпадает с и тогда возможны три случая:
- .
- Тогда — это подстрока , но равна и тогда очевидно, что мы не можем увеличить значение и надо рассматривать уже .
- и .
- Тогда равна , которая является подстрокой строки , которая равна . Значит точно можно сказать, что равна и тогда очевидно, что можно увеличить до .
- и .
- Тогда равна , которая не является подстрокой строки (так как). Так как известно, что не равен , то равны лишь и и тогда понятно, что .
Псевдокод
int[] buildZFunctionFromPrefixFunction(P : int[])
int[] Z = int[n]
for i = 1 to n - 1
if P[i] > 0
Z[i - P[i] + 1] = P[i]
Z[0] = n
int t
for i = 1 to n - 1
t = i
if Z[i] > 0
for j = 1 to Z[i] - 1
if Z[i + j] > Z[j]
break
Z[i + j] = min(Z[j], Z[i] - j)
t = i + j
i = t
return Z
Время работы
Время работы алгоритма составляет , так как в первом цикле пробегается один раз каждая позиция в массиве , а во втором цикле перезаписывается каждая позиция массива не более одного раза.
