Изменения
→Построение Z-функции по префикс-функции
[[Файл:Case three.png|300px|thumb|right|'''Случай третий''']]
=== Постановка задачи ===
Дан массив с корректной [[Префикс-функция | префикс-функцией]] для строки <tex>s</tex>, получить за <tex>O(n)</tex> массив с Z-функцией для строки <tex>s</tex>.
<br>
===Описание алгоритма===
===Псевдокод===
'''int[]''' buildZFunctionFromPrefixFunction(P : '''int'''[] P) '''int''' n = P.length; '''int'''[] Z = new '''int'''[n] '''for'''(i = 1 '''intto''' i = n - 1; i < n; i++) '''if'''(P[i])> 0
Z[i - P[i] + 1] = P[i]
Z[0] = n;
'''int''' t
'''for'''(i = 1 '''intto''' i = 1; i < n - 1; i++) t = i; '''if'''(Z[i])> 0 '''for'''(j = 1 '''intto''' j = 1; j < Z[i] && - 1 '''if''' Z[i + j] <= > Z[j]; j++) '''break'''
Z[i + j] = min(Z[j], Z[i] - j)
t = i + j
