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

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

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

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

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

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

шаг 0: суффиксное дерево для сжатой строки

* Строка [math]s[/math] разбивается на пары: [math] 12 11 12 21 22 21 [/math]
* Пары сортирутся поразрядной сортировкой: [math]11 12 12 21 21 22 [/math].
* Удаляются копии: [math]11 12 21 22[/math].
* Парам даются номера (условно, в массиве они и так есть): [math]11-(0), 12-(1), 21-(2), 22-(3)[/math]
* Создаётся новая строка из номеров пар: 1 0 1 2 3 2
* Из полученной строки создаётся суффикcное дерево:

шаг 1: построение нечетного дерева

Определение:

Нечетное дерево [math]T^{odd}_s[/math] является деревом суффиксов для строки [math]s[/math], узлы-листья которого ограничены нечетными позициями [math]1,3,5,{...} [/math] строки [math]s\$[/math].

шаг 2: построение четного дерева по нечетному

шаг 3: слияние четного и нечетного дерева

шаг 4: построение LCP-дерева

шаг 5: построение суффиксного дерева по LCP и слитому