497
правок
Изменения
Нет описания правки
{{В разработке}}
'''Алгоритм Фарача''' — алгоритм построения [[Сжатое суффиксное дерево|суффиксного дерева]] для заданной строки <tex>s</tex>, ( <tex>| s | = N) </tex> который выполняется за время <tex>O(N)</tex>, при этом даже не требуется выполнения условия конечности алфавита. Такая эффективность достигается за счет того, что строковые последовательности определяются на индексированном алфавите или, что эквивалентно, на целочисленном алфавите <tex>\Sigma = \{1, 2 {...}\dots , k\}</tex>, при этом накладывается дополнительное условие, что <tex>k \in O(N)</tex>. Такие алфавиты часто встречаются на практике.
{{Определение
|definition= Четное дерево <tex>T^{even}_s</tex> является деревом суффиксов для строки <tex>s</tex>, узлы-листья
которого ограничены нечетными позициями <tex>2,4,6,{...} \dots </tex> строки <tex>s\$</tex>.}}
Из дерева сжатой строки получаем частичное (чётное) дерево исходной строки. Частичное потому в нём будут только половина суффиксов, т.е. тех которые стоят в чётных позициях. :
{{Определение
|definition= Нечетное дерево <tex>T^{odd}_s</tex> является деревом суффиксов для строки <tex>s</tex>, узлы-листья
которого ограничены нечетными позициями <tex>1,3,5,{...} \dots </tex> строки <tex>s\$</tex>.}}
Из чётного дерева, нужно получить нечётное дерево (дерево из суффиксов в нечётных позициях). Для этого можно взять суффиксный массив чётного дерева, отрезать первые символы, и выполнить стабильную сортировку по оставшимся первым символам:
