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