Изменения
→Шаг 1: суффиксное дерево для сжатой строки
* Пары сортируются устойчивой сотрировкой (удобно сортировать поразрядной, так число разрядов мало, размер алфавита — <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>
* В исходной строке пары заменяются на номера: <tex>1 0 1 2 3 2</tex>
* Из полученной строки вдвое меньшего размера рекурсивно создаётся [[Сжатое суффиксное дерево | суффикcное дерево]] тем же алгоритмом:
