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