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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Источники информации: добавлена категория)
(Добавил построение строки)
Строка 62: Строка 62:
 
       '''if''' zf[i] == m  
 
       '''if''' zf[i] == m  
 
         '''return''' i
 
         '''return''' i
 +
 +
 +
==Построение строки по Z-функции==
 +
===Постановка задачи===
 +
Восстановить строку по Z-функции за <tex>O(n)</tex>, считая алфавит ограниченным. Если нам нужен неограниченный алфавит, то будем считать, то мощность алфавита равна длине получаемой строки.
 +
 +
===Описание алгоритма===
 +
Пусть в массиве <tex>z</tex> хранятся значения Z-функции, в <tex>s</tex> будет записан ответ. Пойдем по массиву <tex>z</tex> слева направо.
 +
 +
Нужно узнать значение <tex>s[i]</tex>. Для этого посмотрим на значение <tex>z[i]</tex>: если <tex>z[i] = 0</tex>, тогда в <tex>s[i]</tex> запишем ещё не использованный символ или последний использованный символ алфавита, если мы уже использовали все символы. Если <tex>z[i] \neq 0</tex>, то нам нужно записать префикс длины <tex>z[i]</tex> строки <tex>s</tex>. Но если при посимвольном записывании этого префикса в конец строки <tex>s</tex> мы нашли такой <tex>j</tex> (индекс последнего символа строки), что <tex>z[j]</tex> больше, чем длина оставшейся незаписанной части префикса, то мы перестаём писать этот префикс и пишем префикс длиной <tex>z[j]</tex> строки <tex>s</tex>.
 +
 +
=== Реализация ===
 +
'''string''' buildFromZ(z : '''int'''[]):
 +
  '''string''' s = "a"
 +
  '''int''' prefixLength = 1 <font color=green>// длина префикса, который мы записываем</font>
 +
  '''int''' j <font color=green>// позиция символа в строке, который будем записывать</font>
 +
  '''for''' i = 0 '''to''' z.length - 1
 +
      <font color=green>// мы не пишем какой-то префикс и не будем писать новый</font>
 +
      '''if''' z[i] = 0 '''and''' prefixLength = 0
 +
          s += new character <font color=green>// если нового символа нет, то берём последний использованный</font>
 +
      <font color=green>// нам нужно запомнить, что мы пишем префикс </font>
 +
      '''if''' z[i] > prefixLength '''and'''
 +
          prefixLength = z[i]
 +
          j = 0
 +
      <font color=green>// пишем префикс</font>
 +
      '''if''' prefixLength > 0 '''and'''
 +
          s += s[j]
 +
          j++
 +
          prefixLength--     
 +
  '''return''' s
 +
 +
===Доказательство корректности алгоритма===
 +
 +
Докажем, что если нам дали корректную Z-функцию, то наш алгоритм построит строку с такой же Z-функцией.
 +
 +
Пусть <tex>z</tex> — данная Z-функция, строку <tex>s</tex> построил наш алгоритм, <tex>q</tex> — массив значений Z-функции для <tex>s</tex>.
 +
 +
Очевидно, что если <tex>z[i] = 0</tex>, то и <tex>q[i] = 0</tex>, так как <tex>s[i] \ne s[0]</tex> (в результате алгоритма мы получаем, что <tex>s[i] \neq a</tex>, а <tex>s[0] = a</tex>).
 +
 +
Рассмотрим значения <tex>z[i] \ne 0</tex>. В этом случае мы писали префикс исходной строки, его часть или данный префикс полностью содержался в другом префиксе.
 +
#Очевидно, что если мы записали префикс полностью, то <tex>q[i] = z[i]</tex>.
 +
#Если префикс лежит внутри другого префикса, который мы уже пишем, то этот же префикс есть в префиксе исходной строки и Z-функции от него совпадают с Z-функциями рассматриваемого префикса (рассматривается первый случай).
 +
#Рассмотрим случай, когда мы записали часть префикса и прервались для написания нового. Тогда в префиксе самой строки будет часть рассматриваемого префикса и часть нового префикса, то есть символы совпадут. Тогда <tex>q[i] = z[i]</tex>.
  
 
== См. также ==
 
== См. также ==

Версия 15:26, 27 марта 2016

Определение:
Z-функция (англ. Z-function) от строки [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(s : string):
   int[] zf = int[n]
   for i = 1 to 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(|S|)[/math], так как каждая позиция пробегается не более двух раз: при попадании в диапазон от [math]left[/math] до [math]right[/math] и при высчитывании Z-функции простым циклом.

Псевдокод

 int[] zFunction(s : string):
   int[] zf = int[n]
   int left = 0, right = 0
   for i = 1 to 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] — длина образца.
Образуем строку s = pattern + # + text, где # — символ, не встречающийся ни в text, ни в pattern. Вычисляем Z-функцию от этой строки. В полученном массиве, в позициях в которых значение Z-функции равно [math]|\texttt{pattern}|[/math], по определению начинается подстрока, совпадающая с pattern.

Псевдокод

 int substringSearch(text : string, pattern : string):
   int[] zf = zFunction(pattern + '#' + text)
   for i = m + 1 to n + 1
     if zf[i] == m 
       return i


Построение строки по Z-функции

Постановка задачи

Восстановить строку по Z-функции за [math]O(n)[/math], считая алфавит ограниченным. Если нам нужен неограниченный алфавит, то будем считать, то мощность алфавита равна длине получаемой строки.

Описание алгоритма

Пусть в массиве [math]z[/math] хранятся значения Z-функции, в [math]s[/math] будет записан ответ. Пойдем по массиву [math]z[/math] слева направо.

Нужно узнать значение [math]s[i][/math]. Для этого посмотрим на значение [math]z[i][/math]: если [math]z[i] = 0[/math], тогда в [math]s[i][/math] запишем ещё не использованный символ или последний использованный символ алфавита, если мы уже использовали все символы. Если [math]z[i] \neq 0[/math], то нам нужно записать префикс длины [math]z[i][/math] строки [math]s[/math]. Но если при посимвольном записывании этого префикса в конец строки [math]s[/math] мы нашли такой [math]j[/math] (индекс последнего символа строки), что [math]z[j][/math] больше, чем длина оставшейся незаписанной части префикса, то мы перестаём писать этот префикс и пишем префикс длиной [math]z[j][/math] строки [math]s[/math].

Реализация

string buildFromZ(z : int[]):
  string s = "a"
  int prefixLength = 1 // длина префикса, который мы записываем
  int j // позиция символа в строке, который будем записывать
  for i = 0 to z.length - 1
      // мы не пишем какой-то префикс и не будем писать новый
      if z[i] = 0 and prefixLength = 0
          s += new character // если нового символа нет, то берём последний использованный
      // нам нужно запомнить, что мы пишем префикс 
      if z[i] > prefixLength and
          prefixLength = z[i]
          j = 0
      // пишем префикс
      if prefixLength > 0 and
          s += s[j]
          j++
          prefixLength--       
  return s

Доказательство корректности алгоритма

Докажем, что если нам дали корректную Z-функцию, то наш алгоритм построит строку с такой же Z-функцией.

Пусть [math]z[/math] — данная Z-функция, строку [math]s[/math] построил наш алгоритм, [math]q[/math] — массив значений Z-функции для [math]s[/math].

Очевидно, что если [math]z[i] = 0[/math], то и [math]q[i] = 0[/math], так как [math]s[i] \ne s[0][/math] (в результате алгоритма мы получаем, что [math]s[i] \neq a[/math], а [math]s[0] = a[/math]).

Рассмотрим значения [math]z[i] \ne 0[/math]. В этом случае мы писали префикс исходной строки, его часть или данный префикс полностью содержался в другом префиксе.

  1. Очевидно, что если мы записали префикс полностью, то [math]q[i] = z[i][/math].
  2. Если префикс лежит внутри другого префикса, который мы уже пишем, то этот же префикс есть в префиксе исходной строки и Z-функции от него совпадают с Z-функциями рассматриваемого префикса (рассматривается первый случай).
  3. Рассмотрим случай, когда мы записали часть префикса и прервались для написания нового. Тогда в префиксе самой строки будет часть рассматриваемого префикса и часть нового префикса, то есть символы совпадут. Тогда [math]q[i] = z[i][/math].

См. также

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