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