Изменения

Пойдем по массиву <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 = 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>+</tex> количество <tex>break</tex>. Количество значений установленных <tex>— n</tex>. А число <tex>break</tex> тоже будет не больше <tex>n</tex>, так как каждый <tex>break</tex> переводит внешний цикл на следующую итерацию, то есть число операции будет не больше <tex> 2 \cdot n</tex> откуда получаем асимптотику <tex>O(n)</tex>. Рассмотрим корректность алгоритма. Предположим, что наш алгоритм неправильно посчитал какие-то значение <tex>p[i]</tex>. Пусть <tex>ans[1..n]</tex> это массив, содержащий корректную префикс-функцию. Рассмотрим позицию в которой наш алгоритм посчитал некорректно, пусть это позиция <tex>i</tex>. Заметим, что <tex>ans[i]\geqslant p[i]</tex> так как алгоритм записывает длину подстроки, оканчивающуюся на <tex>i-</tex>ом символе, соответственно правильный ответ, не может быть меньше нашего. Предположим, что <tex>ans[i] > p[i]</tex>, посмотрим на значение <tex>z[i - ans[i] + 1]</tex> оно больше либо равно <tex>ans[i]</tex>. Но тогда наш алгоритм бы записал в <tex>p[i]</tex> корректное значение.