Изменения

Пусть <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 \leqslant j < z[i] </tex> , значение <tex>p[i + j] </tex> будет не меньше, чем длина подстроки с <tex> i </tex> по <tex> i + j</tex>, что равно <tex>j + 1</tex> (как изображено на рисунке).

Также заметим, что если мы уже установили в какую-то позицию значение с позиции <tex>k</tex>, где <tex>k < i</tex>, то такое изменение с позиции <tex> i </tex> только уменьшит значение <tex> p[i + 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 + 1,</tex> где <tex>j</tex> пробегает все значения <tex> 0.. \dots z[i] - 1</tex>, пока не наткнемся на уже инициализированный элемент. Слева от него все значения тоже нет смысла обновлять, поэтому прерываем эту итерацию.

Теперь посчитаем асимптотику алгоритмаУбедимся, что алгоритм работает за линейное время (см. псевдокод). Каждый элемент устанавливается ровно один раз. Дальше на нем может случиться только <tex>\mathrm{break}</tex>. Поэтому в итоге внутренний цикл суммарно отработает за количество установленных значений и количество <tex>\mathrm{break}</tex>. Количество установленных значений установленных {{---}} <tex>— n</tex>. А число <tex>\mathrm{break}</tex> тоже будет не больше <tex>n</tex>, так как каждый <tex>\mathrm{break}</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> корректное значение.