33
правки
Изменения
→Доказательство корректности алгоритма
Докажем корректность индукцией по длине массива префикс-функции полученной строки. Для начала заметим, что на предыдущие значения массива <tex> q </tex> прибавление нового символа не влияет, так как при подсчёте префикс-функции на <tex> i </tex>-ой позиции рассматриваются символы на позициях не больше <tex> i </tex>. Поэтому достаточно показать, что очередное значение префикс-функции будет вычислено правильно.
* База очевидна для строки длины <tex>1</tex>.
* Переход: пусть до <tex>n</tex>-ой позиции мы построили строку, что <tex>p[01..n - 1] = q[01..n - 1]</tex>. Возможны два случая:
** <tex>p[n] = 0</tex>. Тогда мы добавляем новый символ, поэтому <tex>q[n]</tex> тоже будет равно <tex>0</tex>.
** <tex>p[n] > 0</tex>. Бордер строки <tex> s[01..n - 1] </tex> имеет длину <tex> p[n-1] = q[n-1] </tex>. Поэтому если дописать к строке <tex> s </tex> символ <tex> s[q[n]] </tex>, то бордер нашей новой строки <tex> s[01..n] </tex> станет равен <tex> p[n] </tex>, как можно увидеть на [[Префикс-функция#Эффективный алгоритм | рисунке]].
== См. также ==
