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