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>. Такие алфавиты часто встречаются на практике.
Важно помнить, что алгоритм скорее теоретический, чем практический, а основная ценность его заключается в том, что размер алфавита может быть произвольным.
= Описание алгоритма =
