Изменения

Пойдем по массиву <tex>z</tex> слева направо, заметим, что если <tex>z[i] > 0, </tex> то для всех элементов с индексом <tex>i + j</tex>, где <tex>0 \leqslant j < z[i] </tex> значение <tex>p[i + j] </tex> будет не меньше, чем <tex>j + 1, </tex> в силу определения префикс и <tex>Z</tex>{{---}} функции. Также заметим, что если мы уже установили значение в какое-то <tex>p[k]</tex> то менять уже не нужно, так как это только уменьшит значение <tex>p[k]</tex>, так как если мы установили в <tex>j</tex>{{---}}ую позицию с позиции <tex>k</tex>, где <tex>k < i</tex>, поэтому можно только уменьшить. В итоге получаем алгоритм: идем слева направо по массиву <tex>z</tex> и пусть мы сейчас находимся на позиции <tex>i</tex>, тогда пытаемся записать в <tex>p</tex> от позиции <tex>i + z[i] - 1 </tex> до <tex>i</tex> значение <tex> j - i + 1,</tex> где <tex>j</tex> пробегает все значения <tex> 0.. z[i] - 1</tex>. В итоге каждый элемент в <tex>p</tex> будет просмотрен не более двух раз, откуда получаем асимптотику <tex>O(n).</tex>

[[Файл:ZP2ZP3.jpg|800px]]