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

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

Алгоритм Фарача — алгоритм построения суффиксного дерева для заданной строки [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ное дерево:

суфдерево для сжатой строки

ID	LCP	STR
1	0	0 1 2 3 2
0	0	1 0 1 2 3 2
2	1	1 2 3 2
3	0	2 3 2
5	1	2
4	0	3 2

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

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

Четное дерево [math]T^{even}_s[/math] является деревом суффиксов для строки [math]s[/math], узлы-листья которого ограничены нечетными позициями [math]2,4,6,{...} [/math] строки [math]s\$[/math].

Из дерева сжатой строки получаем частичное (чётное) дерево исходной строки. Частичное потому в нём будут только половина суффиксов, т.е. тех которые стоят в чётных позициях. :

Очевидно, что для этого достаточно умножить все расстояния в дереве на 2

Корректируются все развилки дерева (так как они могут совпадать в первых символах)

ID	LCP	STR
2	0	1112212221
0	1	121112212221
4	2	12212221
6	0	212221
10	2	21
8	1	2221

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

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

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

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

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

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