3622
правки
Изменения
→Доказательство корректности алгоритма
Докажем, что если нам дали корректную префикс-функцию, то наш алгоритм построит строку с такой же префикс-функцией. Также заметим, что строк с такой префикс-функцией может быть много, и алгоритм строит только одну из них.
Пусть <tex>p</tex> {{---}} данная префикс-функция, <tex>s'</tex> {{---}} правильная строка, строку <tex>s</tex> построил наш алгоритм, <tex> q </tex> {{---}} массив значений префикс-функции для <tex>s</tex>.
Докажем корректность индукцией по длине массива префикс-функции полученной строки. Для начала заметим, что на предыдущие значения массива <tex> q </tex> прибавление нового символа не влияет, так как при подсчёте префикс-функции на <tex> i </tex>-ой позиции рассматриваются символы на позициях не больше <tex> i </tex>. Поэтому достаточно показать, что очередное значение префикс-функции будет вычислено правильно.
