497
правок
Изменения
→Шаг 4: слияние четного и нечетного дерева
Далее необходимо найти эффективный способ слияния нечетного и четного деревьев в одно дерево <tex>T_s</tex>. Слияние будем производить, начиная с корней деревьев.
Предположим, что для каждого узла деревьев <tex>T_s^{odd}</tex> и <tex>T_s^{even}</tex> выходящие из них ребра занесены в специальные списки, где они '''упорядочены ''' в возрастающем лексикографическом порядке подстрок, которые представляют эти ребра. Пусть каждое ребро будет дополнительно "помечено" своим первым символом. Возьмем по одному ребру из этих списков у каждого дереваодинаковыми метками(о одном списке не может быть ребер с одинаковыми метками, так как это сжатые суффиксные деревья), обработаем их, и рекурсивно спустимся в их поддеревья. Если для ребра из одного списка не оказалось ребра с такой же меткой из другого, то в поддеревья, очевидно, не спускаемся, так как там нечего сливать.Очевидно, манипуляции со списками работают за динейное время, так как сами списки упорядочены лексикограяичеси(похже на сортировку слиянием).
Алгоритм просматривает только первые буквы подстрок, представленных ребрами деревьев <tex>T_s^{odd}</tex> и <tex>T_s^{even}</tex>, пусть это будут буквы <tex>\lambda^{odd}</tex> и <tex>\lambda^{even}</tex>. Тогда:
