Z-функция

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Z-фу́нкция от строки S — массив Z, каждый элемент которого Z[i] равен длине наиболее длинного префикса начинающегося с позиции i суффикса строки S, который одновременно является и префиксом всей строки S. Значение Z-функции в нулевой позиции обычно равно или нулю, или длине всей строки; далее будем придерживаться первого варианта.

Часто Z-функцию записывают в виде вектора длиной . Например, для строки «abcdabscabcdabia» Z-функция будет такой:

Z(abcdabscabcdabia) = [0, 0, 0, 0, 2, 0, 0, 0, 6, 0, 0, 0, 2, 0, 0, 1].

Z-функция используется в различных алгоритмах обработки строк. В частности, с её помощью можно быстро решать задачу о поиске вхождения одной строки в другую (поиск по образцу).

Алгоритм вычисления[править | править код]

Символы строк нумеруются с 0.

Будем хранить индексы L и R, обозначающие начало и конец префикса с наибольшим найденным на данный момент значением R. Изначально .

Пусть нам известны значения Z-функции для позиций 1...i − 1. Попробуем вычислить значение Z-функции для позиции i. Если , рассмотрим значение Z-функции для позиции . Если , то , так как мы находимся в подстроке, совпадающей с префиксом всей строки. Если же , то необходимо досчитать значение Z[i] простым циклом, перебирающим символы после R, пока не найдется символ, не совпадающий с соответствующим символом из префикса. После этого изменяем, значение L на i и значение R на номер последнего символа, совпавшего с соответствующим символом из префикса.

Если , то считаем значение Z[i] простым циклом, сравнивающим символы подстроки начинающейся с i-го символа и соответствующие символы из префикса. Когда будет найдено несоответствие или будет достигнут конец строки, изменяем значение L на i и значение R на номер последнего символа, совпавшего с соответствующим символом из префикса.

Скорость работы[править | править код]

Время работы алгоритма, вычисляющего значение Z-функции строки S оценивается в . Докажем это.

Рассмотрим i-й символ строки. В алгоритме он рассматривается не более двух раз: первый раз, когда попадает в отрезок , и второй раз при вычислении Z[i].

Таким образом цикл обрабатывает не более итераций.

Примеры использования[править | править код]

1) Z-функцию можно использовать для поиска образца T в строке S,

2) Зная Z-функцию строки, можно однозначно восстановить префикс-функцию этой строки, и наоборот.

Пример реализации на Python[править | править код]

 1 def z_func(s):
 2   s += '$'
 3   l, r = 0, 0
 4   z = [0] * len(s)
 5   for i in range(1, len(s)):
 6     z[i] = max(0, min(z[i - l], r - i))
 7     while s[z[i]] == s[i + z[i]]:
 8       z[i] += 1
 9     if i + z[i] > r:
10       l, r = i, i + z[i]
11   return z[:-1]

См. также[править | править код]

Ссылки[править | править код]