79
правок
Изменения
м
→Критерий корректности значений префикс-функции
== Критерий корректности значений префикс-функции ==
{{Задача
|definition = Дан массив значений префикс-функции некоторой строки <tex>s</tex>, необходимо проверить, корректен ли он за <tex>O(|s|)</tex>. Так же узнать размер минимального алфавита, при котором он корректен.
}}
=== Решение ===
Проверим, правда ли выполняется формула неравенство <tex>0 \leqslant p[i + 1] \leqslant p[i] + 1</tex> из доказательства выше.Найдем минимальный алфавит, при котором префикс-функция корректна. Если значение префикс-функции в текущей ячейке больше нуля, буква известна и алфавит не нуждается в добавлении новой буквы. Иначе, необходимо исключить все ранее известные буквы, возвращаясь и проверяя для меньших префиксов.
=== Псевдокод ===
'''return''' '''false'''
'''return''' '''true'''
'''int''' minimal_alphabet('''int'''[] p):
int c = 1
s[0] = 0
'''for''' i = 1 '''to''' p.length - 1
if p[i] == 0
fill(used, false)
k = p[i - 1]
while k > 0
used[s[k]] = '''true'''
k = p[k - 1]
s[i] = -1
'''for''' j = 1 '''to''' c
if !used[j]
s[i] = j;
break
if s[i] == -1
s[i] = c++
else
s[i] = s[p[i] - 1]
'''return''' c
== См. также ==
