668
правок
Изменения
→Доказательство корректности алгоритма
Переход: Пусть до <tex>n</tex>-ой позиции мы построили строку, что <tex>p[1..n - 1] = q[1..n - 1]</tex>. Возможно два варианта,
<tex>1)</tex> <tex>p[n] = 0</tex>. Тогда мы добавляем новый символ, поэтому <tex>q[n]</tex> тоже будет равно <tex>0</tex>.Также, предыдущие значения <tex>q</tex> не поменяются и останутся верными.
<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>q[n] > p[n]</tex>. Но этого не может быть, так как тогда бы в строке <tex>s</tex> существовала большая подстрока оканчивающаяся на <tex>n</tex>-ом символе, что противоречит тому, что массив <tex>p</tex> корректный.
