Z-функция

Определение:

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].

Время работы

Этот алгоритм работает за [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]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].

Для правильной работы алгоритма, будем считать значение [math]z[0][/math] равным нулю.

Заметим, что не всегда удастся восстановить строку с ограниченным алфавитом неподходящего размера. Например, для строки [math]abacaba[/math] массив Z-функций будет [math][0, 0, 1, 0, 3, 0, 1][/math]. Используя двоичный алфавит, мы получим строку [math]abababa[/math], но её массив Z-функций отличается от исходного. Ошибка восстановления строки возникла, когда закончились новые символы алфавита.

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

Время работы

Этот алгоритм работает за O(|S|), так как мы один раз проходим по массиву Z-функций.

Реализация

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

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

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

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

Записали префикс, начинающийся в [math]i[/math]. После пишем префикс, начинающийся в [math]j[/math]. Этот префикс не изменит символы первого префикса.

Рассмотрим похожий алгоритм, но с более худшей асимптотикой. Отличие будет в том, что при [math]z[i] \gt 0[/math] мы будем писать префикс полностью и возвращаться в позицию [math]i + 1[/math]. Рассмотрим каждый шаг этого алгоритма. Если [math]z[i] = 0[/math], то мы пишем символ, отличный от первого символа строки, поэтому [math]q[i] = 0[/math], а значит [math]q[i] = z[i][/math]. Если [math]z[i] \gt 0[/math], то при записи [math]s[i][/math] мы будем получать [math]q[i] = z[i][/math], потому что мы переписали префикс строки. Но далее мы можем переписать этот префикс другим префиксом. Заметим, что новый префикс будет содержаться и в префиксе самой строки, поэтому пересечение двух префиксов будет состоять из одинаковых символов. Значит, префикс не будет изменяться, как и значение [math]q[i][/math]. Тогда массив [math]q[/math] совпадает с [math]z[/math].

Покажем, что этот алгоритм эквивалентен нашему алгоритму. Когда мы пишем разные префиксы, то возможны три варианта: они не пересекаются (начало и конец одного префикса не принадлежат другому), один лежит внутри другого (начало и конец префикса принадлежит другому), они пересекаются (начало одного префикса пренадлежит другому, но конец не принадлежит).

• Если префиксы не пересекаются, то в алгоритме они не влияют друг на друга.

• Если префикс лежит внутри другого префикса, то записав большой префикс мы запишем и малый, поэтому не нужно возвращаться к началу малого префикса.

• Если префиксы пересекаются, то нам нужно переписать часть префикса, который начинается раньше, и начать писать другой префикс (начало этого префикса запишет конец префикса, начинающегося раньше).

Таким образом, алгоритмы эквивалентны и наш алгоритм тоже корректен.

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

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

Задача:

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

Случай первый

Случай второй

Случай третий

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

Пусть префикс функция хранится в массиве [math]P[0 ... n - 1][/math]. Z-функцию будем записывать в массив [math]Z[0 ... n-1][/math]. Заметим, что если [math]P[i]\gt 0[/math], то мы можем заявить, что [math]Z[i-P[i]+1][/math] будет не меньше, чем [math]P[i][/math].

Так же заметим, что после такого прохода в [math]Z[1][/math] будет максимальное возможное значение. Далее будем поддерживать инвариант: в [math]Z[i][/math] будет максимальное возможное значение.

Пусть в [math]Z[i] = z \gt 0[/math], рассмотрю [math]j\lt z[/math], [math]Z[j]=k[/math] и [math]Z[i+j]=k_1[/math]. Заметим, что [math]s[0 ... z-1][/math] совпадает с [math]s[i...i+z-1][/math] и тогда возможны три случая:

1. [math]k\lt k_1[/math].

   Тогда [math]s[0...k-1][/math] — это подстрока [math]s[0...k_1-1][/math], но [math]s[0...k_1-1][/math] равна [math]s[i+j...i+j+k_1-1][/math] и тогда очевидно, что мы не можем увеличить значение [math]Z[i+j][/math] и надо рассматривать уже [math]i=i+j[/math].

2. [math]k\lt z-j[/math] и [math]k\gt k_1[/math].

   Тогда [math]s[0...k-1][/math] равна [math]s[j...j+k-1][/math], которая является подстрокой строки [math]s[0...z-1][/math], которая равна [math]s[i...i+z-1][/math]. Значит точно можно сказать, что [math]s[0...k-1][/math] равна [math]s[i+j...i+j+k-1][/math] и тогда очевидно, что [math]Z[i+j][/math] можно увеличить до [math]k[/math].

3. [math]k\gt z-j[/math] и [math]k\gt k_1[/math].

   Тогда [math]s[0...k-1][/math] равна [math]s[j...j+k-1][/math], которая не является подстрокой строки [math]s[0...z-1][/math] (так как[math]j+k-1 \gt z[/math]). Так как известно, что [math]s[z][/math] не равен [math] s[i+z][/math], то равны лишь [math]s[0...z-j][/math] и [math]s[i+j...i+z-1][/math] и тогда понятно, что [math]Z[i+j]=z-j[/math].

Псевдокод

int[] buildZFunctionFromPrefixFunction(P : int[])
  int[] Z = int[n]
  for i = 1 to n - 1
     if P[i] > 0
        Z[i - P[i] + 1] = P[i]
  Z[0] = n
  int t
  for i = 1 to n - 1
     t = i
     if Z[i] > 0
        for j = 1 to Z[i] - 1
           if Z[i + j] > Z[j]
              break
           Z[i + j] = min(Z[j], Z[i] - j)
           t = i + j
     i = t
  return Z

Время работы

Время работы алгоритма составляет [math]O(n)[/math], так как в первом цикле пробегается один раз каждая позиция в массиве [math]P[/math], а во втором цикле перезаписывается каждая позиция массива [math]Z[/math] не более одного раза.

См. также

• Префикс-функция
• Алгоритм Кнута-Морриса-Пратта

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

• Поиск подстроки и смежные вопросы — Хабр
  
• Википедия — Z-функция
  
• Codeforces — Переход между Z- и префикс- функциями