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