Изменения

|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\, \mathinner{\ldotp\ldotp}ldots \, i + k] = s[0 \mathinner{\ldotp\ldotp} ldots k]</tex>. <!-- проинлайнил \twodots из clrscode -->

'''if''' i + zf[i] >= right

Для правильной работы алгоритма, будем считать значение <tex>z[0]</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>.

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

[[Файл: Префиксы2.png|400px]]* Если префиксы пересекаются, то нам нужно переписать часть префикса, который начинается раньше, и начать писать другой префикс (начало этого префикса запишет конец префикса, начинающегося раньше).Если полностью переписать префикс, начинающийся раньше, то мы не сможем восстановить префикс, который начинался раньше конца первого префикса.[[Файл: Префиксы3.png|400px]]

|definition= Дан массив с корректной [[Префикс-функция | префикс-функцией]] для строки <tex>s</tex>, . Требуется получить массив с Z-функцией для строки <tex>s</tex>.

Пусть префикс функция хранится в массиве <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>.

Пусть в <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>b_1 \subset s[0...k-1]</tex> {{---}} это подстрока <tex>s[0...k_1-1]</tex>, но <tex>s[0...\ldots k_1-1]</tex> равна <tex>=s[i+j...\ldots i+j+k_1-1]</tex> и тогда очевидно, что мы не можем увеличить значение <tex>Z[i+j]</tex> и надо рассматривать уже <tex>i=i+j</tex>.

#: Тогда <tex>s[0...k-1]</tex> равна <tex>s[j...j+k-1]</tex>, которая является подстрокой строки <tex>s[0...z-1]</tex>, которая равна <tex>b_1 = b_2 \subset b_3 = s[i...\ldots i+z-1]</tex>. Значит точно можно сказать, что <tex>s[0...k-1]</tex> равна <tex>\Rightarrow b_1 = s[i+j...\ldots i+j+k-1]</tex> и тогда очевидно, что <tex>Z[i+j]</tex> можно увеличить до <tex>k</tex>.

#: Тогда <tex>s[0...k-1]b_1 = b_2 </tex> равна , но <tex>s[j...j+k-1]b_2</tex>, которая не является подстрокой строки <tex>s[0...z-1]b_3</tex> (так как<tex>j+k-1 > z</tex>). Так как известно, что <tex>s[z]</tex> не равен <tex> \ne s[i+z]</tex>, то равны лишь <tex>s[0...\ldots z-j]</tex> и <tex>= s[i+j...\ldots i+z-1]</tex> и тогда понятно, что <tex>Z[i+j]=z-j</tex>.

'''int[]''' buildZFunctionFromPrefixFunction(P : '''int'''[n])

'''int''' ti = 1 '''forwhile''' i = 1 < n '''toint''' n - 1 t = i

i = t+ 1

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