Изменения

** <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> должен продолжить префикс меньшей длины, а в текущее значение префикс-функции запишется как раз длина нового [[Период_и_бордер,_их_связь#Определения|бордера]]. Для этого будут использованы значения префикс-функции с меньшими индексами, которые посчитаны верно, опять же по предположению индукции.

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

*[[Z-функция|Z-функция]]