748
правок
Изменения
→Построение Z-функции по префикс-функции
Таким образом, мы рассмотрели все случаи, при которых <tex>z[i] \ne 0</tex>, и показали корректность восстановления блока.
==Построение Z-функции по префикс-функции==[[Файл:Case one.png|300px|thumb|right|Случай первый]][[Файл:Case two.png|300px|thumb|right|Случай второй]][[Файл:Case three.png|300px|thumb|right|Случай третий]]
=== Постановка задачи ===
Дан массив с корректной [[Префикс-функция | префикс-функцией]] для строки <tex>s</tex>, получить за <tex>O(n)</tex> массив с Z-функцией для строки <tex>s</tex>.
<br>
===Описание алгоритма===
<br>
Пусть префикс функция хранится в массиве <tex>P[0 ... n - 1]</tex>. Z-функцию будем записывать в массив <tex>Z[0 ... n-1]</tex>. Заметим, что если <tex>P[i]>0</tex>, то мы можем заявить, что <tex>Z[i-P[i]+1]</tex> будет не меньше, чем <tex>P[i]</tex>.
<br>
Так же заметим, что после такого прохода в <tex>Z[1]</tex> будет максимальное возможное значение. Далее будем поддерживать инвариант: в <tex>Z[i]</tex> будет максимальное возможное значение.
<br>
<br>Пусть в <tex>Z[i] = z > 0</tex>, рассмотрю <tex>j<kz</tex>, <tex>Z[j]=k</tex> и <tex>Z[i+j]=k_1</tex>. Заметим, что <tex>s[0 ... z-1]</tex> совпадает с <tex>s[i...i+z-1]</tex> и тогда возможны три случая:# <tex>k<k_1</tex>. Тогда мы не можем увеличить значение <tex>Z[i+j]</tex> и надо рассматривать уже <tex>i=i+j</tex>. <!--(см картинку)-->
# <tex>k<z-j</tex> и <tex>k>k_1</tex>. Тогда очевидно, что <tex>Z[i+j]</tex> можно увеличить до <tex>k</tex>. <!--(см картинку)-->
# <tex>k>z-j</tex> и <tex>k>k_1</tex>. Тогда понятно, что <tex>Z[i+j]=z-j</tex>. <!--(см картинку)-->
<br>
<br>
<br>
<br>
<br>
<br>
===Псевдокод===
'''int[]''' buildZFunctionFromPrefixFunction('''int'''[] P)
'''int''' n = P.length;
'''int'''[] Z=new '''int'''[n]
'''for'''('''int''' i = 1; i < n; i++)
'''if'''(P[i])
