79
правок
Изменения
м
→Решение
=== Решение ===
Если выполняется неравенство <tex>0 \leqslant p[i + 1] \leqslant p[i] + 1</tex>, то мы можем построить строку из алгоритма выше, значит она префикс-функция корректна.
Найдем минимальный алфавит, при котором префикс-функция корректна. Если значение префикс-функции в текущей ячейке больше нуля, буква известна и алфавит не нуждается в добавлении новой буквы. Иначе, необходимо исключить все ранее известные буквы, возвращаясь и проверяя для меньших префиксов. Если все уже известные буквы использованы, понятно что, необходимо добавить новую букву.