Изменения

Перейти к: навигация, поиск

Z-функция

413 байт добавлено, 16:50, 14 апреля 2016
Псевдокод
'''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)
i = t
'''return''' Z
===Время работы===
Время работы алгоритма составляет <tex>O(n)</tex>, так как в первом цикле пробегается один раз каждая позиция в массиве <tex>P</tex>, а во втором цикле перезаписывается каждая позиция массива <tex>Z</tex> не более одного раза.
== См. также ==
Анонимный участник

Навигация