Z-функция — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Эффективный алгоритм поиска: оформление)
(Определение)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
|definition = '''Z-функция''' от строки <tex>S</tex> и позиции <tex>x</tex> — это длина максимального префикса подстроки, начинающейся с позиции <tex>x</tex> в строке <tex>S</tex>, который одновременно является и префиксом всей строки <tex>S</tex>. Иными словами, <tex>z[i](s) = \max k \mid s[i\, \mathinner{\ldotp\ldotp}\, i + k] = s[0\, \mathinner{\ldotp\ldotp}\, k]</tex>. <!-- проинлайнил \twodots из clrscode -->
+
|definition = '''Z-функция''' от строки <tex>S</tex> и позиции <tex>x</tex> — это длина максимального префикса подстроки, начинающейся с позиции <tex>x</tex> в строке <tex>S</tex>, который одновременно является и префиксом всей строки <tex>S</tex>. Более формально, <tex>Z[i](s) = \max k \mid s[i\, \mathinner{\ldotp\ldotp}\, i + k] = s[0\, \mathinner{\ldotp\ldotp}\, k]</tex>. <!-- проинлайнил \twodots из clrscode -->
  
 
Значение Z-функции от первой позиции не определено, поэтому его обычно приравнивают к нулю или к длине строки.
 
Значение Z-функции от первой позиции не определено, поэтому его обычно приравнивают к нулю или к длине строки.
Строка 6: Строка 6:
 
'''Примечание:''' далее в конспекте символы строки нумеруются с нуля.
 
'''Примечание:''' далее в конспекте символы строки нумеруются с нуля.
  
[[Файл:Zfunc-examp.png|500px]]
+
[[Файл:Zfunc-examp.png|мини|500px|Строка и её Z-функция]]
  
 
== Тривиальный алгоритм ==
 
== Тривиальный алгоритм ==

Версия 21:52, 7 июня 2015

Определение:
Z-функция от строки [math]S[/math] и позиции [math]x[/math] — это длина максимального префикса подстроки, начинающейся с позиции [math]x[/math] в строке [math]S[/math], который одновременно является и префиксом всей строки [math]S[/math]. Более формально, [math]Z[i](s) = \max k \mid s[i\, \mathinner{\ldotp\ldotp}\, i + k] = s[0\, \mathinner{\ldotp\ldotp}\, k][/math]. Значение Z-функции от первой позиции не определено, поэтому его обычно приравнивают к нулю или к длине строки.

Примечание: далее в конспекте символы строки нумеруются с нуля.

Строка и её Z-функция

Тривиальный алгоритм

Простая реализация за [math]O(n^2)[/math], где [math]n[/math] — длина строки. Для каждой позиции [math]i[/math] перебираем для неё ответ, начиная с нуля, пока не обнаружим несовпадение или не дойдем до конца строки.

Псевдокод

 int[] zFunction(string s)
   int[] zf = int[n]
   for i = 1 .. n − 1
     while i + zf[i] < n and s[zf[i]] == s[i + zf[i]]
       zf[i]++
   return zf

Эффективный алгоритм поиска

Z-блоком назовем подстроку с началом в позиции [math]i[/math] и длиной [math]Z[i][/math].
Для работы алгоритма заведём две переменные: [math]left[/math] и [math]right[/math] — начало и конец Z-блока строки [math]S[/math] с максимальной позицией конца [math]right[/math] (среди всех таких Z-блоков, если их несколько, выбирается наибольший). Изначально [math]left=0[/math] и [math]right=0[/math]. Пусть нам известны значения Z-функции от [math]0[/math] до [math]i-1[/math]. Найдём [math]Z[i][/math]. Рассмотрим два случая.

  1. [math]i \gt right[/math]:
    Просто пробегаемся по строке [math]S[/math] и сравниваем символы на позициях [math]S[i+j][/math] и [math]S[j][/math]. Пусть [math]j[/math] первая позиция в строке [math]S[/math] для которой не выполняется равенство [math]S[i+j] = S[j][/math], тогда [math]j[/math] это и Z-функция для позиции [math]i[/math]. Тогда [math]left = i, right = i + j - 1[/math]. В данном случае будет определено корректное значение [math]Z[i][/math] в силу того, что оно определяется наивно, путем сравнения с начальными символами строки.
  2. [math]i \leqslant right[/math]:
    Сравним [math]Z[i - left] + i[/math] и [math]right[/math]. Если [math]right[/math] меньше, то надо просто наивно пробежаться по строке начиная с позиции [math]right[/math] и вычислить значение [math]Z[i][/math]. Корректность в таком случае также гарантирована. Иначе мы уже знаем верное значение [math]Z[i][/math], так как оно равно значению [math]Z[i - left][/math]. Z-func.png

Время работы

Этот алгоритм работает за [math]O(\lvert S\rvert)[/math], так как каждая позиция пробегается не более двух раз: при попадании в диапазон от [math]left[/math] до [math]right[/math] и при высчитывании Z-функции простым циклом.

Псевдокод

 int[] zFunction(string s)
   int[] zf = int[n]
   int left = 0, right = 0
   for i = 1 .. 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-функции

[math]n[/math] — длина текста. [math]m[/math] — длина образца.
Образуем строку [math]s = \texttt{needle} + \# + \texttt{source}[/math], где [math]\#[/math] — символ, не встречающийся ни в [math]\texttt{source}[/math], ни в [math]\texttt{needle}[/math]. Вычисляем Z-функцию от этой строки. В полученном массиве, в позициях в которых значение Z-функции равно [math]|\texttt{needle}|[/math], по определению начинается подстрока, совпадающая с [math]\texttt{needle}[/math].

Псевдокод

 int substringSearch(string source, string needle)
   int[] zf = zFunction(needle + '#' + source)
   for i = m + 1 .. n + m
     if zf[i] == m 
       return i

См. также

Источники информации