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