Z-функция

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

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

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

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

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

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

Псевдокод

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

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

Время работы

Этот алгоритм работает за $O(|S|)$, так как каждая позиция пробегается не более двух раз: при попадании в диапазон от $left$ до $right$ и при высчитывании 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-функции

$n$ — длина текста. $m$ — длина образца.
Образуем строку s = pattern + # + text, где # — символ, не встречающийся ни в text, ни в pattern. Вычисляем Z-функцию от этой строки. В полученном массиве, в позициях в которых значение Z-функции равно $|\texttt{pattern}|$, по определению начинается подстрока, совпадающая с 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-функции за $O(n)$, считая алфавит ограниченным.

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

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

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

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

Алгоритм всегда сможет построить строку по корректному массиву значений Z-функции, если в алфавите больше одного символа.

Если строить строку по некорректному массиву значений Z-функции, то мы получим какую-то строку, но массив значений 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-функцией.

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

Так как значение в $z[0]$ неопределено, то мы рассматриваем ненулевые индексы массива $z$.

Если $z[i] = 0$, то по алгоритму $s[i]$ будет отличаться от $s[0]$. Тогда, при подсчёте Z-функции для полученной строки, мы получим, что $q[i] = 0$, ведь $s[i] \neq s[0]$. Значит, если $z[i] = 0$, то $z[i] = q[i]$.

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

• Мы полностью записали рассматриваемый блок длиной $z[i]$. По определению Z-функции $q[i] = z[i]$.
• Мы записали часть рассматриваемого блока $b_1$ и прервались, чтобы записать новый блок $b_2$. Допустим, что мы полностью написали блок $b_1$, а после написали блок $b_2$. В таком случае мы переписали символы в пересечении двух блоков. Эти символы совпадают, иначе массив $z$ был бы некорректным. Поэтому блок $b_1$ запишется правильно и полностью. Этот случай мы уже рассмотрели выше.
• Рассматриваемый блок $b_1$ полностью покрывается блоком $b_2$, который мы уже пишем. Допустим, что мы напишем блок $b_1$ после того, как написали блок $b_2$. При корректном массиве $z$ символы в пересечении двух блоков совпадут. Тогда мы можем просто рассматривать блок $b_1$ аналогично одному из предыдущих случаев.

Таким образом, мы доказали, что значения массивов $q$ и $z$ совпадают.

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

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

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

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

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

Задача:

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

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

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

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

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

1. $k\lt k_1$.

   Тогда очевидно, что мы не можем увеличить значение $Z[i+j]$ и надо рассматривать уже $i=i+j$.

2. $k\lt z-j$ и $k\gt k_1$.

   Тогда очевидно, что $Z[i+j]$ можно увеличить до $k$.

3. $k\gt z-j$ и $k\gt k_1$.

   Тогда понятно, что $Z[i+j]=z-j$.

Псевдокод

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

Время работы

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

См. также

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

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

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