Изменения

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

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

** <tex>p[n] = 0</tex>. Тогда мы добавляем новый символ, поэтому <tex>q[n]</tex> тоже будет равно <tex>0</tex>.

** <tex>p[n] > 0</tex>. По свойствам префикс-функции <tex> s'[p[n]] = s'[n] </tex> {{---}} суффикс и префикс строки <tex> s' </tex> длины <tex> p[n] </tex> продолжаются одним символом, значит, надо на текущую позицию строки <tex> s </tex> поставить символ <tex> s[p[n]] </tex>. Если значение префикс-функции увеличивается, значит, текущим символом продолжается префикс длины <tex> p[n - 1] </tex>, а из свойств следует, что <tex> p[n - 1] \geqslant p[n] - 1 </tex>. По предположению индукцию значение <tex> q[n - 1] </tex> будет вычислено верно. А если значение префикс-функции не увеличивается, значит, символ <tex> s[n] </tex> должен продолжить префикс меньшей длины, а в текущее значение префикс-функции запишется как раз длина нового [[Период_и_бордер,_их_связь#Определения|бордера]]. Для этого будут использованы значения префикс-функции с меньшими индексами, которые посчитаны верно, опять же по предположению индукции.

== См. также ==