333
правки
Изменения
→Шаг 1: суффиксное дерево для сжатой строки
* Строка <tex>s</tex> разбивается на пары подряд идущих символов: <tex> \langle 12\rangle \langle 11\rangle \langle 12\rangle \langle 21\rangle \langle 22\rangle \langle 21\rangle </tex>
*: (если символов нечетное число {{---}} последняя пара дополняется специальным символом <tex>\$</tex>)
* Пары сортируются устойчивой сотрировкой (удобно сортировать [[Цифровая_сортировка | поразрядной]], так как число разрядов мало, размер алфавита — <tex>O(n)</tex>, то время работы сортировки — линейное): <tex> \langle 11 \rangle \langle 12\rangle \langle 12\rangle \langle 21\rangle \langle 21\rangle \langle22\rangle </tex>.
* Удаляются копии: <tex> \langle 11\rangle \langle 12\rangle \langle 21\rangle \langle 22\rangle </tex>.
* Парам даются номера (условно, в массиве они и так есть): <tex>\langle 11 \rangle -(0), \langle 12\rangle -(1), \langle 21\rangle - (2), \langle 22\rangle-(3)</tex>
