497
правок
Изменения
→шаг 3: слияние четного и нечетного дерева
== шаг 3: слияние четного и нечетного дерева ==
Далее необходимо найти эффективный способ слияния нечетного и четного деревьев в одно дерево <tex>Т_s</tex>. Слияние будем производить начиная с корня.
Предположим, что для каждого узла деревьев <tex>Т_s^{odd}</tex> и <tex>Т_s^{even}</tex> выходящие из них ребра занесены в специальные списки, где они упорядочены в возрастающем лексикографическом порядке подстрок, которые представляют эти
ребра. Алгоритм слияния деревьев просматривает только первые буквы подстрок, представленных ребрами деревьев <tex>Т_s^{odd}</tex> и <tex>Т_s^{even}</tex>, пусть это будут буквы <tex>\lambda^{odd}</tex> и <tex>\lambda^{even}</tex>. Тогда:
* если <tex>\lambda^{odd}</tex> <tex>\ne</tex> <tex>\lambda^{even}</tex>, определяется поддерево, соответствующее меньшей из этих букв, и без изменений присоединяется к узлу-родителю;
* если <tex>\lambda^{odd}</tex> <tex>=</tex> <tex>\lambda^{even}</tex> и длины подстрок, представленных соответствующими ребрами, равны, в дерево слияния к текущему узлу добавляются два сына: один — из четного дерева, другой — из нечетного;
* если <tex>\lambda^{odd}</tex> <tex>=</tex> <tex>\lambda^{even}</tex> и длины подстрок, представленных соответствующими ребрами, различны, в дерево слияния к текущему узлу добавляются два узла, находящиеся на одном нисходящем пути, при этом ближайший узел будет соответствовать более короткой подстроке.
Если начать эту процедуру для корней нечетного и четного деревьев, далее она рекурсивно выполняется для корней всех поддеревьев, которые, возможно, уже содержат узлы из нечетного и четного деревьев, поскольку ранее мог быть реализован случай <tex>\lambda^{odd}</tex> <tex>=</tex> <tex>\lambda^{even}</tex>. Так как время манипулирования с любым ребром этих деревьев фиксированно, то общее время слияния деревьев составит <tex>O(N)</tex>.
В результате описанных действий получится дерево <tex>M_x</tex>,в котором будут присутствовать поддеревья, которые прошли процедуру сличния, и которые ее избежали (т.е были перенесены в дерево <tex>M_x</tex> без изменений).
== шаг 4: построение LCP-дерева ==
== шаг 5: построение суффиксного дерева по LCP и слитому ==
