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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм поиска)
м (rollbackEdits.php mass rollback)
 
(не показаны 82 промежуточные версии 13 участников)
Строка 1: Строка 1:
==Определение==
+
{{Определение
Z-функция от строки <tex>S</tex> и позиции <tex>x</tex> — это длина максимального префикса подстроки, начинающейся с позиции <tex>x</tex> в строке <tex>S</tex>, который одновременно является и префиксом всей строки <tex>S</tex>.
+
|definition = '''Z-функция''' (англ. ''Z-function'') от строки <tex>S</tex> и позиции <tex>x</tex> — это длина максимального префикса подстроки, начинающейся с позиции <tex>x</tex> в строке <tex>S</tex>, который одновременно является и префиксом всей строки <tex>S</tex>. Более формально, <tex>Z[i](s) = \max k \mid s[i\, \ldots \, i + k] = s[0 \ldots k]</tex>. <!-- проинлайнил \twodots из clrscode -->
==Алгоритм поиска==
+
 
===Задача===
+
Значение Z-функции от первой позиции не определено, поэтому его обычно приравнивают к нулю или к длине строки.
Дана строка <tex>S</tex>. Необходимо построить массив <tex>Z</tex>, такой, что <tex>Z[i]</tex> является префикс функцией данной строки с позиции <tex>i</tex>
+
}}
 +
'''Примечание:''' далее в конспекте символы строки нумеруются с нуля.
 +
 
 +
[[Файл:Zfunc-examp.png|мини|500px|Строка и её Z-функция]]
 +
 
 +
== Тривиальный алгоритм ==
 +
 
 +
Простая реализация за <tex>O(n^2)</tex>, где <tex>n</tex> — длина строки. Для каждой позиции <tex>i</tex> перебираем для неё ответ, начиная с нуля, пока не обнаружим несовпадение или не дойдем до конца строки.
 +
 
 +
=== Псевдокод ===
 +
  '''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-блоком назовем подстроку с началом в позиции <tex>i</tex> и длиной <tex>Z[i]</tex>.<br>
 +
Для работы алгоритма заведём две переменные: <tex>left</tex> и <tex>right</tex> — начало и конец Z-блока строки <tex>S</tex> с максимальной позицией конца <tex>right</tex> (среди всех таких Z-блоков, если их несколько, выбирается наибольший). Изначально <tex>left=0</tex> и <tex>right=0</tex>.
 +
Пусть нам известны значения Z-функции от <tex>0</tex> до <tex>i-1</tex>. Найдём <tex>Z[i]</tex>.
 +
Рассмотрим два случая.
 +
 
 +
# <tex>i > right</tex>:<br><!--
 +
-->Просто пробегаемся по строке <tex>S</tex> и сравниваем символы на позициях <tex>S[i+j]</tex> и <tex>S[j]</tex>.<!--
 +
-->Пусть <tex>j</tex> первая позиция в строке <tex>S</tex> для которой не выполняется равенство <tex>S[i+j] = S[j]</tex>, тогда <tex>j</tex> это и Z-функция для позиции <tex>i</tex>. Тогда <tex>left = i, right = i + j - 1</tex>. В данном случае будет определено корректное значение <tex>Z[i]</tex> в силу того, что оно определяется наивно, путем сравнения с начальными символами строки.
 +
# <tex>i \leqslant right</tex>:<br><!--
 +
-->Сравним <tex>Z[i - left] + i</tex> и <tex>right</tex>. Если <tex>right</tex> меньше, то надо просто наивно пробежаться по строке начиная с позиции <tex>right</tex> и вычислить значение <tex>Z[i]</tex>. Корректность в таком случае также гарантирована.<!--
 +
-->Иначе мы уже знаем верное значение <tex>Z[i]</tex>, так как оно равно значению <tex>Z[i - left]</tex>.
 +
[[Файл:z-func.png]]
 +
 
 +
=== Время работы ===
 +
Этот алгоритм работает за <tex>O(|S|)</tex>, так как каждая позиция пробегается не более двух раз: при попадании в диапазон от <tex>left</tex> до <tex>right</tex> и при высчитывании 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-функции ==
 +
<tex>n</tex> — длина текста. <tex>m</tex> — длина образца. <br>
 +
Образуем строку <tt>s = pattern + # + text</tt>, где <tt>#</tt> — символ, не встречающийся ни в <tt>text</tt>, ни в <tt>pattern</tt>. Вычисляем Z-функцию от этой строки.
 +
В полученном массиве, в позициях в которых значение Z-функции равно <tex>|\texttt{pattern}|</tex>, по определению начинается подстрока, совпадающая с <tt>pattern</tt>.
 +
 
 +
=== Псевдокод ===
 +
  '''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-функции==
 +
{{Задача
 +
|definition= Необходимо восстановить строку по Z-функции, считая алфавит ограниченным.
 +
}}
 
===Описание алгоритма===
 
===Описание алгоритма===
Для работы алгоритма заведём две переменные: <tex>left</tex> и <tex>right</tex> — начало и конец наибольшего префикса строки <tex>S</tex> с максимальным значением <tex>right</tex>. Изначально <tex>left=0</tex> и <tex>right=0</tex>.
+
Пусть в массиве <tex>z</tex> хранятся значения Z-функции, в <tex>s</tex> будет записан ответ. Пойдем по массиву <tex>z</tex> слева направо.
  
Пусть нам известны значения Z-функции от <tex>0</tex> до <tex>i-1</tex>. Найдём <tex>Z[i]</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>.
Есть два случая: <tex>i > right</tex> и <tex>i \leq right</tex>.
+
 
 +
Для правильной работы алгоритма будем считать значение <tex>z[0]</tex> равным нулю.
 +
 
 +
Заметим, что не всегда удастся восстановить строку с ограниченным алфавитом неподходящего размера. Например, для строки <tex>abacaba</tex> массив Z-функций будет <tex>[0, 0, 1, 0, 3, 0, 1]</tex>. Используя двоичный алфавит, мы получим строку <tex>abababa</tex>, но её массив Z-функций отличается от исходного. Ошибка восстановления строки возникла, когда закончились новые символы алфавита.
 +
 
 +
Если строить строку по некорректному массиву значений Z-функции, то мы получим какую-то строку, но массив значений Z-функций от неё будет отличаться от исходного.
 +
 
 +
=== Время работы ===
 +
Этот алгоритм работает за O(|S|), так как мы один раз проходим по массиву Z-функций.
 +
=== Реализация ===
 +
'''string''' buildFromZ(z : '''int'''[], alphabet : '''char'''[]):
 +
  '''string''' s = ""
 +
  '''int''' prefixLength = 0 <font color=green>// длина префикса, который мы записываем</font>
 +
  '''int''' j <font color=green>// позиция символа в строке, который будем записывать</font>
 +
  '''int''' newCharacter = 0 <font color=green>// индекс нового символа</font>
 +
  '''for''' i = 0 '''to''' z.length - 1
 +
      <font color=green>// мы не пишем какой-то префикс и не будем писать новый</font>
 +
      '''if''' z[i] = 0 '''and''' prefixLength = 0
 +
          if newCharacter < alphabet.length
 +
              s += alphabet[newCharacter]
 +
              newCharacter++
 +
          else
 +
              s += alphabet[newCharacter - 1]
 +
      <font color=green>// нам нужно запомнить, что мы пишем префикс </font>
 +
      '''if''' z[i] > prefixLength
 +
          prefixLength = z[i]
 +
          j = 0
 +
      <font color=green>// пишем префикс</font>
 +
      '''if''' prefixLength > 0
 +
          s += s[j]
 +
          j++
 +
          prefixLength--     
 +
  '''return''' s
 +
 
 +
===Доказательство корректности алгоритма===
 +
 
 +
Докажем, что если нам дали корректную Z-функцию, то наш алгоритм построит строку с такой же Z-функцией.
 +
 
 +
Пусть <tex>z</tex> — данная Z-функция, строку <tex>s</tex> построил наш алгоритм, <tex>q</tex> — массив значений Z-функции для <tex>s</tex>. Покажем, что массивы <tex>q</tex> и <tex>z</tex> будут совпадать.
 +
 
 +
[[Файл: Запись_префикса.png|330px|thumb|right|Записали префикс, начинающийся в <tex>i</tex>. После пишем префикс, начинающийся в <tex>j</tex>. Этот префикс не изменит символы первого префикса.]]
 +
 
 +
Рассмотрим похожий алгоритм, но с более худшей асимптотикой. Отличие будет в том, что при <tex>z[i] > 0</tex> мы будем писать префикс полностью и возвращаться в позицию <tex>i + 1</tex>. Рассмотрим каждый шаг этого алгоритма. Если <tex>z[i] = 0</tex>, то мы пишем символ, отличный от первого символа строки, поэтому <tex>q[i] = 0</tex>, а значит <tex>q[i] = z[i]</tex>. Если <tex>z[i] > 0</tex>, то при записи <tex>s[i]</tex> мы будем получать <tex>q[i] = z[i]</tex>, потому что мы переписали префикс строки. Но далее мы можем переписать этот префикс другим префиксом. Заметим, что новый префикс будет содержаться и в префиксе самой строки, поэтому пересечение двух префиксов будет состоять из одинаковых символов. Значит, префикс не будет изменяться, как и значение <tex>q[i]</tex>. Тогда массив <tex>q</tex> совпадает с <tex>z</tex>.
 +
 
 +
Покажем, что этот алгоритм эквивалентен нашему алгоритму. Когда мы пишем разные префиксы, то возможны три варианта: они не пересекаются (начало и конец одного префикса не принадлежат другому), один лежит внутри другого (начало и конец префикса принадлежит другому), они пересекаются (начало одного префикса пренадлежит другому, но конец не принадлежит).
 +
* Если префиксы не пересекаются, то в алгоритме они не влияют друг на друга.
 +
[[Файл: Префиксы1.png|400px]]
 +
* Если префикс лежит внутри другого префикса, то записав большой префикс мы запишем и малый, поэтому не нужно возвращаться к началу малого префикса.
 +
[[Файл: Префиксы2.png|400px]]
 +
* Если префиксы пересекаются, то нам нужно переписать часть префикса, который начинается раньше, и начать писать другой префикс (начало этого префикса запишет конец префикса, начинающегося раньше). Если полностью переписать префикс, начинающийся раньше, то мы не сможем восстановить префикс, который начинался раньше конца первого префикса.
 +
[[Файл: Префиксы3.png|400px]]
 +
 
 +
Таким образом, алгоритмы эквивалентны и наш алгоритм тоже корректен.
 +
 
 +
==Построение Z-функции по префикс-функции==
 +
 
 +
{{Задача
 +
|definition=  Дан массив с корректной [[Префикс-функция | префикс-функцией]] для строки <tex>s</tex>. Требуется получить массив с Z-функцией для строки <tex>s</tex>.
 +
}}[[Файл:Case one.png|300px|thumb|right|'''Случай первый''']]
 +
[[Файл:Case two.png|300px|thumb|right|'''Случай второй''']]
 +
[[Файл:Case three.png|300px|thumb|right|'''Случай третий''']]
 +
 
 +
<br>
  
 +
===Описание алгоритма===
 +
<br>
 +
Пусть префикс функция хранится в массиве <tex>P[0 \ldots n - 1]</tex>. Z-функцию будем записывать в массив <tex>Z[0 \ldots n-1]</tex>. Заметим, что если <tex>P[i]>0</tex>, то мы можем заявить, что <tex>Z[i-P[i]+1]</tex> будет не меньше, чем <tex>P[i]</tex>.
 +
<br>
 +
<br>
 +
Так же заметим, что после такого прохода в <tex>Z[1]</tex> будет максимальное возможное значение. Далее будем поддерживать инвариант: в <tex>Z[i]</tex> будет максимальное возможное значение.
 
<br>
 
<br>
1) <tex>i > right</tex>:<br>
+
<br>
Просто пробегаемся по строке <tex>S</tex> и сравниваем символы на позициях <tex>S[i+j]</tex> и <tex>S[j]</tex>.
+
Пусть в <tex>Z[i] = z > 0</tex>, рассмотрю <tex>j<z</tex>, <tex>Z[j]=k</tex> и <tex>Z[i+j]=k_1</tex>. Пусть <tex>b_1=s[0 \ldots k-1]</tex>, <tex>b_2=s[j \ldots j+k-1]</tex>, <tex>b_3=s[0 \ldots z-1]</tex>. Тогда заметим, что <tex>b_3 = s[i \ldots i+z-1]</tex> и тогда возможны три случая:
Пусть <tex>j</tex> первая позиция в строке <tex>S</tex> для которой не выполняется равенство <tex>S[i+j] == S[j]</tex>, тогда <tex>j</tex> это и Z-функция для позиции <tex>i</tex>. Тогда <tex>left = i, right = i + j - 1</tex>.  
+
 
 +
# <tex>k<k_1</tex>.
 +
#: Тогда <tex>b_1 \subset s[0 \ldots k_1-1]=s[i+j \ldots i+j+k_1-1]</tex> и тогда очевидно, что мы не можем увеличить значение <tex>Z[i+j]</tex> и надо рассматривать уже <tex>i=i+j</tex>.
 +
# <tex>k<z-j</tex> и <tex>k>k_1</tex>.
 +
#: Тогда <tex>b_1 = b_2 \subset b_3 = s[i \ldots i+z-1] \Rightarrow b_1 = s[i+j \ldots i+j+k-1]</tex> и тогда очевидно, что <tex>Z[i+j]</tex> можно увеличить до <tex>k</tex>.
 +
# <tex>k>z-j</tex> и <tex>k>k_1</tex>.  
 +
#: Тогда <tex>b_1 = b_2 </tex>, но <tex>b_2</tex> не является подстрокой строки <tex>b_3</tex> (так как<tex>j+k-1 > z</tex>). Так как известно, что <tex>s[z] \ne s[i+z]</tex>, то <tex>s[0 \ldots z-j] = s[i+j \ldots i+z-1]</tex> и тогда понятно, что <tex>Z[i+j]=z-j</tex>.  
  
 
<br>
 
<br>
2) <tex>i \le right</tex>:<br>
 
Сравним <tex>Z[i - left] + i</tex> и <tex>right</tex>. Если <tex>right</tex> меньше, то надо просто пробежаться по строке начиная с позиции <tex>right</tex> и вычислить значение <tex>Z[i]</tex>.
 
Иначе мы уже знаем значение <tex>Z[i]</tex>, так как оно равно значению <tex>Z[i - left]</tex>.
 
 
<br>
 
<br>
[[Файл:z-func.png]]
+
<br>
 +
<br>
 +
<br>
 +
<br>
 +
 
 +
===Псевдокод===
 +
'''int[]''' buildZFunctionFromPrefixFunction(P : '''int'''[n])
 +
  '''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''' i = 1
 +
  '''while''' i < n
 +
      '''int''' 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 + 1
 +
  '''return''' Z
 +
 
 +
===Время работы===
 +
Внешний цикл <tex>\mathrm{while}</tex> отработает за <tex>O(n)</tex> итераций, так как внутри него <tex>i</tex> увеличивается не менее чем на <tex>1</tex>. А внутренний цикл выполнит суммарно не более <tex>O(n)</tex> итераций, так как после него <tex>i</tex> увеличится на количество итераций внутреннего цикла, но <tex>i</tex> не может увеличиться более чем на <tex>n</tex>, так как каждое значение <tex>Z[i]</tex> не может превзойти <tex>n</tex>.
 +
 
 +
== См. также ==
 +
* [[Префикс-функция]]
 +
* [[Алгоритм Кнута-Морриса-Пратта]]
  
===Время работы алгоритма===
+
== Источники информации ==
Этот алгоритм работает за <tex>O(\lvert S\rvert)</tex>, так как каждая позиция пробегается не более двух раз: при попадании в диапазон от <tex>left</tex> до <tex>right</tex> и при высчитывании Z-функции простым циклом.
+
* [http://habrahabr.ru/post/113266/ Поиск подстроки и смежные вопросы — Хабр]<br>
 +
* [[wikipedia:ru:Z-функция | Википедия — Z-функция]]<br>
 +
* [http://codeforces.ru/blog/entry/9612/ Codeforces — Переход между Z- и префикс- функциями]
  
===Код алгоритма===
+
[[Категория: Дискретная математика и алгоритмы]]
  int[] z(String p) {
+
[[Категория: Поиск подстроки в строке]]
    int[] ans = new int[p.length()];
+
[[Категория:Точный поиск]]
    ans[0] = 0;
 
    int n = p.length();
 
    int left = 0;
 
    int right = 0;
 
    for (int i = 1; i < n; i++) {
 
      if (i > right) {
 
        int j = 0;
 
        while (i + j < n && p.charAt(i+j) == p.charAt(j)) {
 
          j++;
 
        }
 
        ans[i] = j;
 
        left = i;
 
        right = i + j - 1;
 
      } else {
 
        if (ans[i - left] < right - i + 1) {
 
          ans[i] = ans[i - left];
 
        } else {
 
          int j = 1;
 
          while (j + right < n && p.charAt(j+right-i) == p.charAt(right + j)) {
 
            j++;
 
          }
 
          ans[i] = right + j - i;
 
          left = i;
 
          right = right + j - 1;
 
        }
 
      }
 
    }
 
    return ans;
 
}
 

Текущая версия на 19:12, 4 сентября 2022

Определение:
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\, \ldots \, i + k] = s[0 \ldots 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]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].

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

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

Префиксы1.png

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

Префиксы2.png

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

Префиксы3.png

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

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

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


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


Пусть префикс функция хранится в массиве [math]P[0 \ldots n - 1][/math]. Z-функцию будем записывать в массив [math]Z[0 \ldots 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]b_1=s[0 \ldots k-1][/math], [math]b_2=s[j \ldots j+k-1][/math], [math]b_3=s[0 \ldots z-1][/math]. Тогда заметим, что [math]b_3 = s[i \ldots i+z-1][/math] и тогда возможны три случая:

  1. [math]k\lt k_1[/math].
    Тогда [math]b_1 \subset s[0 \ldots k_1-1]=s[i+j \ldots 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]b_1 = b_2 \subset b_3 = s[i \ldots i+z-1] \Rightarrow b_1 = s[i+j \ldots 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]b_1 = b_2 [/math], но [math]b_2[/math] не является подстрокой строки [math]b_3[/math] (так как[math]j+k-1 \gt z[/math]). Так как известно, что [math]s[z] \ne s[i+z][/math], то [math]s[0 \ldots z-j] = s[i+j \ldots i+z-1][/math] и тогда понятно, что [math]Z[i+j]=z-j[/math].







Псевдокод

int[] buildZFunctionFromPrefixFunction(P : int[n])
  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 i = 1
  while i < n 
     int 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 + 1
  return Z

Время работы

Внешний цикл [math]\mathrm{while}[/math] отработает за [math]O(n)[/math] итераций, так как внутри него [math]i[/math] увеличивается не менее чем на [math]1[/math]. А внутренний цикл выполнит суммарно не более [math]O(n)[/math] итераций, так как после него [math]i[/math] увеличится на количество итераций внутреннего цикла, но [math]i[/math] не может увеличиться более чем на [math]n[/math], так как каждое значение [math]Z[i][/math] не может превзойти [math]n[/math].

См. также

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