Алгоритм Фараха

Эта статья находится в разработке!

Алгоритм Фарача — алгоритм построения суффиксного дерева для заданной строки $s$, который выполняется за время $O(N)$, при этом даже не требуется выполнения условия конечности алфавита. Такая эффективность достигается за счет того, что строковые последовательности определяются на индексированном алфавите или, что эквивалентно, на целочисленном алфавите $\Sigma = \{1, 2 {...}, a\}$, при этом накладывается дополнительное условие, что $a \in O(N)$. Такие алфавиты часто встречаются на практике.

описание алгоритма

Основная идея алгоритма, заключается в том что мы уменьшаем размер исходной строки. Для этого мы разбиваем символы сходной строки на пару и пронумеровываем их, а из полученных номеров составляем новую строку, которая уже в 2 раза короче.

Мы опишем алгоритм Фарача в виде пяти выполняемых шагов. Используем в качестве примера строку $s = 121112212221$, определенную на алфавите $А = {1, 2}$ (в этом примере N = 12).