497
правок
Изменения
init
{{В разработке}}
'''Алгоритм Фарача''' — алгоритм построения [[Сжатое суффиксное дерево|суффиксного дерева]] для заданной строки <tex>s</tex>, который выполняется за время <tex>O(N)</tex>, при этом даже не требуется выполнения условия конечности алфавита. Такая эффективность достигается за счет того, что строковые последовательности определяются на индексированном алфавите или, что эквивалентно, на целочисленном алфавите <tex>\sigma = {1, 2.... , а}</tex>, при этом накладывается дополнительное условие, что <tex>a \in O(N)</tex>. Такие алфавиты часто встречаются на практике.
Основная идея алгоритма, заключается в том что мы уменьшаем размер исходной строки. Для этого мы разбиваем символы сходной строки на пару и пронумеровываем их, а из полученных номеров составляем новую строку.
'''Алгоритм Фарача''' — алгоритм построения [[Сжатое суффиксное дерево|суффиксного дерева]] для заданной строки <tex>s</tex>, который выполняется за время <tex>O(N)</tex>, при этом даже не требуется выполнения условия конечности алфавита. Такая эффективность достигается за счет того, что строковые последовательности определяются на индексированном алфавите или, что эквивалентно, на целочисленном алфавите <tex>\sigma = {1, 2.... , а}</tex>, при этом накладывается дополнительное условие, что <tex>a \in O(N)</tex>. Такие алфавиты часто встречаются на практике.
Основная идея алгоритма, заключается в том что мы уменьшаем размер исходной строки. Для этого мы разбиваем символы сходной строки на пару и пронумеровываем их, а из полученных номеров составляем новую строку.
