668
правок
Изменения
→Доказательство корректности алгоритма
База очевидна для строки длиной 1
Переход: Пусть до <tex>n</tex> позиции мы построили строку, что <tex>p[1..n- 1] = q[1..n- 1]</tex>Возможно два варианта, 1) p[n] = 0. Тогда мы добавляем новый символ, поэтому q[n] тоже будет равно 02) p[n] > 0.
== Литература ==
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. {{---}} 2-е изд. {{---}} М.: Издательский дом «Вильямс», 2007. {{---}} С. 1296.
