Изменения

Номер каждой пары превращается в номер четного суффикса исходной строки. Раскрываем все пары в суффиксы, а номера в листьях от этого умножатся на <tex>2</tex> очевидным образом:

'''Рис. 2 дерево с раскрытыми парами в суффиксы'''

Эта процедура требует константное время на каждое ребро и константное время на каждую вершину, а значит, на нее требуется линейное время.

'''Рис. 3 все развилки скорректированы'''

* [[Сжатое_суффиксное_дерево#.D0.9F.D0.BE.D1.81.D1.82.D1.80.D0.BE.D0.B5.D0.BD.D0.B8.D0.B5_.D0.B8.D0.B7_.D1.81.D1.83.D1.84.D1.84.D0.B8.D0.BA.D1.81.D0.BD.D0.BE.D0.B3.D0.BE_.D0.BC.D0.B0.D1.81.D1.81.D0.B8.D0.B2.D0.B0 | Построим из нового суффиксного массива дерево]], которое будет уже нечётным, что тоже делается за линейное время.

'''Рис. 4 нечетное дерево'''

Если начать эту процедуру для корней нечётного и чётного деревьев, она рекурсивно выполнится для корней всех поддеревьев, которые, возможно, уже содержат узлы из нечетного и четного деревьев, поскольку ранее мог быть реализован случай <tex>\lambda^{odd}</tex> <tex>=</tex> <tex>\lambda^{even}</tex>. Так как время манипулирования любым ребром этих деревьев фиксировано, то общее время слияния деревьев составит <tex>O(N)</tex>.

'''Рис. 5 Слитое дерево (условно)'''

'''Рис. 6 некоторые ребра прошли процедуру слияния'''

Если дуги совпадают полностью, тогда ничего не делаем, удаляем одну из копий и всё. Если начало для двух дуг совпадает только частично, тогда нужно делать для них общее начало, а ветки, которые на концах, снова развести по разным деревьям (для этого можно во время слияния запомнить их начальный цвет или просто сохранить ссылки на исходные ветки).

'''Рис. 7 откорректированное дерево'''

Для примера как это сделать возьмём строку <tex>10010010101000</tex>:

'''Рис. 8 пример'''

'''Рис. 9 итоговое дерево'''