668
правок
Изменения
→Доказательство корректности алгоритма
Докажем, что если нам дали корректную префикс-функцию, то наш алгоритм построит строку с такой же префикс-функцией. Также заметим, что строк с такой префикс-функцией может быть много, и алгоритм строит только одну из них.
Докажем корректность индукцией по длине массива префикс-функции полученной строки.