668
правок
Изменения
→Описание алгоритма
=== Описание алгоритма ===
Пусть <tex>Z-</tex> функция хранится в массиве <tex>z[1..n],</tex> префикс-функцию будем записывать в массив <tex>p[1..n]</tex>.
Пойдем по массиву <tex>z</tex> слева направо, заметим, что если <tex>z[i] > 0, </tex> то для всех элементов с индексом <tex>i + j</tex>, где <tex>0 < j < Z[i] </tex> значение <tex>P[i + j] </tex> будет не меньше, чем <tex>j + 1 , </tex> в силу определения префикс и <tex>Z</tex> функции.
== См. также ==
