Interested Article - Z-функция

Z-фу́нкция от строки $S$ — массив $Z_{1},\dots ,Z_{n}$ , такой что $Z_{i}$ равен длине наибольшего общего префикса начинающегося с позиции $i$ суффикса строки $S$ и самой строки $S$ . Алгоритм построения был изложен в его книге «Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология» в 1997 году на основе публикации Мейна и Лоренца 1984 года о поиске всех тандемных повторов в строке.

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

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

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

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

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

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

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

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

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

Таким образом цикл обрабатывает не более $2\left|S\right|$ итераций.

Примеры использования

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

См. также

Примечания

(англ.) : Computer Science and Computational Biology — Cambridge University Press , 1997. — 556 p. — ISBN 978-0-511-57493-1 —
Main M. G., Lorentz R. J. (англ.) // — Academic Press , 1984. — Vol. 5, Iss. 3. — P. 422—432. — ISSN ; —

Ссылки

на MAXimal::algo
(недоступная ссылка)

[1] (англ.) : Computer Science and Computational Biology — Cambridge University Press , 1997. — 556 p. — ISBN 978-0-511-57493-1 —

[2] Main M. G., Lorentz R. J. (англ.) // — Academic Press , 1984. — Vol. 5, Iss. 3. — P. 422—432. — ISSN ; —

Строки
Меры схожести строк	Расстояние Дамерау — Левенштейна Расстояние Левенштейна Расстояние Хэмминга Сходство Джаро — Винклера
Поиск подстроки	Алгоритм Бойера — Мура Алгоритм Бойера — Мура — Хорспула Алгоритм Кнута — Морриса — Пратта Алгоритм Рабина — Карпа Префикс-функция Алгоритм Ахо — Корасик
Палиндромы	Дерево палиндромов Алгоритм Манакера
Выравнивание последовательностей	Алгоритм Нидлмана — Вунша Алгоритм Смита — Ватермана
Суффиксные структуры	Суффиксный массив Суффиксный автомат Суффиксное дерево Префиксное дерево
Другое	Синтаксический анализ Сопоставление с образцом Наибольшая общая подпоследовательность Наибольшая общая подстрока

Interested Article - Z-функция

Содержание