668
правок
Изменения
→Доказательство корректности алгоритма
Воспользуемся старыми обозначениями <tex>p</tex> данная префикс-функция, <tex>s</tex> правильная строка, <tex>s1</tex> эту строку построил наш алгоритм, <tex> q </tex> массив значений префикс-функции для <tex>s1</tex>.
Докажем корректность индукцией по индукциидлине массива префикс-функции полученной строки.
База очевидна для строки длиной <tex>1</tex>.
