Изменения
→См. также
Таким образом, мы рассмотрели все случаи, при которых <tex>z[i] \ne 0</tex>, и показали корректность восстановления блока.
==Построение Z-функции по префикс-функции==
=== Постановка задачи ===
Дан массив с корректной [[Префикс-функция | префикс-функцией]] для строки <tex>s</tex>, получить за <tex>O(n)</tex> массив с Z-функцией для строки <tex>s</tex>.
<!-- ===Описание алгоритма=== -->
===Псевдокод===
'''int[]''' buildZFunctionFromPrefixFunction('''int'''[] P)
'''int''' n = P.length;
'''int'''[] Z=new '''int'''[n]
'''for'''('''int''' i = 1; i < n; i++)
'''if'''(P[i])
Z[i - P[i] + 1] = P[i]
Z[0] = n;
'''int''' t
'''for'''('''int''' i = 1; i < n - 1; i++)
t = i;
'''if'''(Z[i] && !Z[i + 1])
'''for'''('''int''' j = 1; j < Z[i] && Z[i + j] <= Z[j]; j++)
Z[i + j] = min(Z[j], Z[i] - j)
t = i + j
i = t
return Z
== См. также ==
* [[Префикс-функция]]
