497
правок
Изменения
→Шаг 1: суффиксное дерево для сжатой строки
=== Шаг 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><\langle 11> <\rangle \langle 12> <\rangle \langle 12> <\rangle \langle 21> <\rangle \langle 21> <22> \rangle \langle22\rangle </tex>.* Удаляются копии: <tex><\langle 11> <\rangle \langle 12> <\rangle \langle 21> <\rangle \langle 22> \rangle </tex>.
* Парам даются номера (условно, в массиве они и так есть): <tex>11-(0), 12-(1), 21-(2), 22-(3)</tex>
* Создаётся новая строка из номеров пар: <tex>1 0 1 2 3 2</tex>
