497
правок
Изменения
Нет описания правки
Мы опишем алгоритм Фарача в виде пяти выполняемых шагов. Используем в качестве примера строку <tex>s = 121112212221</tex>, определенную на алфавите <tex>А = {1, 2} </tex> (в этом примере N = 12).
== шаг 0Шаг 1: суффиксное дерево для сжатой строки==
* Строка <tex>s</tex> разбивается на пары: <tex> 12 11 12 21 22 21 </tex>
|}
== шаг 1Шаг 2: построение четного дерева ==
{{Определение
|definition= Четное дерево <tex>T^{even}_s</tex> является деревом суффиксов для строки <tex>s</tex>, узлы-листья
|}
== шаг 2Шаг 3: построение нечетного по четному ==
{{Определение
|definition= Нечетное дерево <tex>T^{odd}_s</tex> является деревом суффиксов для строки <tex>s</tex>, узлы-листья
|}
== шаг 3Шаг 4: слияние четного и нечетного дерева ==
Далее необходимо найти эффективный способ слияния нечетного и четного деревьев в одно дерево <tex>Т_s</tex>. Слияние будем производить начиная с корня.
В результате описанных действий получится дерево <tex>M_x</tex>,в котором будут присутствовать поддеревья, которые прошли процедуру сличния, и которые ее избежали (т.е были перенесены в дерево <tex>M_x</tex> без изменений).
== шаг 4Шаг 5: удаление двойных дуг ==
[[Файл:Tree101232merged.png|500px|thumb|right]]
Дерево после обработки:
[[Файл:Treestep5_2.jpg|650px|thumb|left|]]
