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