Русская Википедия:Z-функция
Z-фу́нкция от строки <math>S</math> — массив <math>Z_1, \dots, Z_n</math>, такой что <math>Z_i</math> равен длине наибольшего общего префикса начинающегося с позиции <math>i</math> суффикса строки <math>S</math> и самой строки <math>S</math>. Алгоритм построения был изложен Шаблон:Не переведено 5 в его книге «Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология» в 1997 году[1] на основе публикации Мейна и Лоренца 1984 года[2] о поиске всех тандемных повторов в строке.
Z-функция используется в различных алгоритмах обработки строк. В частности, с её помощью можно быстро решать задачу о поиске вхождения одной строки в другую (поиск по образцу).
Алгоритм вычисления
- Символы строк нумеруются с 0.
Будем хранить индексы L и R, обозначающие начало и конец префикса с наибольшим найденным на данный момент значением R. Изначально <math>L = R = 0</math>.
Пусть нам известны значения Z-функции для позиций 1…i − 1. Попробуем вычислить значение Z-функции для позиции i. Если <math>i \in [L..R]</math>, рассмотрим значение Z-функции для позиции <math>j = i - L</math>. Если <math>i + Z[j] \leqslant R</math>, то <math>Z[i] = Z[j]</math>, так как мы находимся в подстроке, совпадающей с префиксом всей строки. Если же <math>i + Z[j] > R</math>, то необходимо досчитать значение Z[i] простым циклом, перебирающим символы после R, пока не найдется символ, не совпадающий с соответствующим символом из префикса. После этого изменяем, значение L на i и значение R на номер последнего символа, совпавшего с соответствующим символом из префикса.
Если <math>i \notin [L..R]</math>, то считаем значение Z[i] простым циклом, сравнивающим символы подстроки начинающейся с i-го символа и соответствующие символы из префикса. Когда будет найдено несоответствие или будет достигнут конец строки, изменяем значение L на i и значение R на номер последнего символа, совпавшего с соответствующим символом из префикса.
Скорость работы
Время работы алгоритма, вычисляющего значение Z-функции строки S оценивается в <math>O(\left| S \right|)</math>. Докажем это.
Рассмотрим i-й символ строки. В алгоритме он рассматривается не более двух раз: первый раз, когда попадает в отрезок , и второй раз при вычислении Z[i].
Таким образом цикл обрабатывает не более <math>2\left| S \right|</math> итераций.
Примеры использования
1) Z-функцию можно использовать для поиска образца T в строке S,
2) Зная Z-функцию строки, можно однозначно восстановить префикс-функцию этой строки, и наоборот.
Пример реализации на Python
def z_func(s):
z = [0] * len(s)
left, right = 0, 0
for i in range(1, len(s)):
z[i] = max(0, min(z[i - left], right - i))
while i + z[i] < len(s) and s[z[i]] == s[i + z[i]]:
z[i] += 1
if i + z[i] > right:
left, right = i, i + z[i]
return z
См. также
Примечания
Ссылки
- Статья на MAXimal::algo
- Задача для проверкиШаблон:Недоступная ссылка
