Z-функция

Z-фу́нкция от строки [math]\displaystyle{ S }[/math] — массив [math]\displaystyle{ Z_1, \dots, Z_n }[/math], такой что [math]\displaystyle{ Z_i }[/math] равен длине наибольшего общего префикса начинающегося с позиции [math]\displaystyle{ i }[/math] суффикса строки [math]\displaystyle{ S }[/math] и самой строки [math]\displaystyle{ S }[/math]. Алгоритм построения был изложен Дэном Гасфилдом в его книге «Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология» в 1997 году на основе публикации Мейна и Лоренца 1984 года о поиске всех тандемных повторов в строке.

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

Алгоритм вычисления

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

Будем хранить индексы L и R, обозначающие начало и конец префикса с наибольшим найденным на данный момент значением R. Изначально [math]\displaystyle{ L = R = 0 }[/math].

Пусть нам известны значения Z-функции для позиций 1…i − 1. Попробуем вычислить значение Z-функции для позиции i. Если [math]\displaystyle{ i \in [L..R] }[/math], рассмотрим значение Z-функции для позиции [math]\displaystyle{ j = i - L }[/math]. Если [math]\displaystyle{ i + Z[j] \leqslant R }[/math], то [math]\displaystyle{ Z[i] = Z[j] }[/math], так как мы находимся в подстроке, совпадающей с префиксом всей строки. Если же [math]\displaystyle{ i + Z[j] \gt R }[/math], то необходимо досчитать значение Z[i] простым циклом, перебирающим символы после R, пока не найдется символ, не совпадающий с соответствующим символом из префикса. После этого изменяем, значение L на i и значение R на номер последнего символа, совпавшего с соответствующим символом из префикса.

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

Скорость работы

Время работы алгоритма, вычисляющего значение Z-функции строки S оценивается в [math]\displaystyle{ O(\left| S \right|) }[/math]. Докажем это.

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

Таким образом цикл обрабатывает не более [math]\displaystyle{ 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
• Задача для проверки (недоступная ссылка)