79
правок
Изменения
м
Нет описания правки
** <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] - 1] </tex>, то бордер нашей новой строки <tex> s[0..n] </tex> станет равен <tex> p[n] </tex>, как можно увидеть на [[Префикс-функция#Эффективный алгоритм | рисунке]].
== Критерий корректности значений префикс-функции ==
{{Задача
|definition = Дан массив значений префикс-функции некоторой строки <tex>s</tex>, необходимо проверить, корректен ли он за <tex>O(|s|)</tex>.
}}
=== Решение ===
Проверим, правда ли выполняется формула <tex>0 \leqslant p[i + 1] \leqslant p[i] + 1</tex> из доказательства выше.
=== Псевдокод ===
'''bool''' is_correct('''int'''[] p):
'''for''' i = 0 '''to''' p.length - 1
'''if''' i > 0 && p[i] > p[i - 1] + 1 || p[i] < 0
'''return''' '''false'''
'''return''' '''true'''
== См. также ==
