Изменения

Докажем корректность индукцией по длине массива префикс-функции полученной строки. Для начала заметим, что на предыдущие значения массива <tex> q </tex> прибавление нового символа не влияет, так как при подсчёте префикс-функции на <tex> i </tex>-ой позиции рассматриваются символы на позициях не больше <tex> i </tex>. Поэтому достаточно показать, что очередное значение префикс-функции будет вычислено правильно.

** <tex>p[n] > 0</tex>. Предположим, что По свойствам префикс-функции <tex>qs'[p[n] \neq p] = s'[n] </tex>. Заметим, что подстрока с {{---}} суффикс и префикс строки <tex>1s' </tex> по длины <tex>p[n]</tex> оканчивается на <tex>n</tex>-ом символе. По предположению индукции наш алгоритм построил правильную строку до <tex>n - 1</tex> символапродолжаются одним символом, следовательнозначит, надо на текущую позицию строки <tex>p[n] \leqslant q[n]s </tex>. Представим, что поставить символ <tex>qs[n] > p[n] </tex>, тогда получается, что префикс с <tex>1..q[n]</tex> в строке <tex>s'</tex>, является подстрокой заканчивающийся на <tex>n</tex>-ом символе, но тогда возникает противоречие с тем, что массив <tex>p</tex> корректный. Также, предыдущие значения <tex>q</tex> не поменяются и останутся верными.