79
правок
Изменения
м
→Восстановление строки по суффиксному массиву
=== Вариант для бесконечного алфавита ===
Так как наш алфавит не ограничен, можно <tex>i</tex>-й в лексикографическом порядке суффикс сопоставить с <tex>i</tex>-й буквой в алфавите.
==== Доказательство корректности ====
Если отсортировать суффиксы, то первые буквы будут расположены как в алфавите.
==== Псевдокод ====
==== Доказательство минимальности ====
Докажем от противного. Пусть, есть решение в котором использовано меньше букв. Тогда найдется позиция в которой, наше решение отличается от минимального, причем в минимальном остается та же буква, как в предыдущем суффиксе, а в нашем появляется новая. Рассмотрим эти два подряд идущих суффикса. В решении выше добавится новая буква, только если продолжение первого суффикса лексикографически больше, чем продолжение второго. Получается, что в минимальном решении первый суффикс лексикографически больше, чем второй, что неверно. Пришли к противоречию.
== Применения ==
