Изменения

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