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