Изменения

Пусть наш алгоритм неправильно посчитал какие-то значение <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> корректное значение.