Изменения

Пойдем по массиву <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> i </tex> по <tex> i + j</tex>, что равно <tex>j + 1</tex> (видно еще из рисунка). Также заметим, что если мы уже установили значение в какое-то <tex>p[k]</tex> то менять уже не нужно, так как если мы установили в <tex>j-</tex>ую позицию с позиции <tex>k</tex>, где <tex>k < i</tex>, то такое изменение только уменьшит значение <tex> p[j]</tex>, действительно, значение после первого присвоения <tex>p_{old}[i + j] = i + j - k + 1 > i + j - i + 1 = j + 1 = p_{new}[i + j]</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> break </tex>. Поэтому в итоге внутренний цикл суммарно отработает за количество установленных значений + количество <tex>break</tex>.В итоге каждый элемент в <tex>p</tex> будет просмотрен не более двух раз, то есть число операции будет не больше <tex> 2 \cdot n</tex> откуда получаем асимптотику <tex>O(n).</tex>