Изменения

'''Алгоритм Фарача (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>. Такие алфавиты часто встречаются на практике.

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

Lля для всех внутренних вершин <tex>u</tex>, ребра всех детей которых начинаются с одинаковых символов, мы создадим новую вершину между <tex>u</tex> и ее детьми. Это можно сделать быстро, так как все ребра, исходящие их любой вершины, лексикографически отсортированы по своим первым двум символам (так как мы сортировали пары номера пар на прошлом шаге). Для каждого ребра нам достоточно достаточно проверить, что его первыей первый символ соответствует первому символу соседнего ребра, и, если так, сделать необходимые исправления. Может быть, что ребра ко всем детям <tex>u</tex> начинаются с одинакового символа, и в этом случае у вершины <tex>u</tex> будет только один ребенок теперь. Ну тогда Тогда удалим <tex>u</tex>.Эта процедура требует требует константное время на каждое ребро и константное время на каждую вершину, а значит, на нее требуется линейное время.

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

Предположим, что для каждого узла деревьев <tex>T_s^{odd}</tex> и <tex>T_s^{even}</tex> выходящие из них ребра занесены в специальные списки, где они '''упорядочены''' в возрастающем лексикографическом порядке подстрок, которые представляют эти ребра. Пусть каждое ребро будет дополнительно "помечено" своим первым символом. Возьмем по одному ребру из этих списков с одинаковыми метками(о в одном списке не может быть ребер с одинаковыми метками, так как это сжатые суффиксные деревья), обработаем их, и рекурсивно спустимся в их поддеревья. Если для ребра из одного списка не оказалось ребра с такой же меткой из другого, то в поддеревья, очевидно, не спускаемся, так как там нечего сливать.Очевидно, манипуляции со списками работают за динейное линейное время, так как сами списки упорядочены лексикограяичеси(похже на сортировку слиянием)лексикографически.

поскольку Поскольку мы рассматриваем только первый символ каждого ребра(то есть делаем вид, что ребра равны, если первые символы у них равны), то мы может можем иногда слить ребрарёбра, которые не должны были быть слиты, но . Однако те, которые надо было слить, точно сольем.

Если начать эту процедуру для корней нечетного нечётного и четного чётного деревьев, далее она рекурсивно выполняется выполнится для корней всех поддеревьев, которые, возможно, уже содержат узлы из нечетного и четного деревьев, поскольку ранее мог быть реализован случай <tex>\lambda^{odd}</tex> <tex>=</tex> <tex>\lambda^{even}</tex>. Так как время манипулирования любым ребром этих деревьев фиксировано, то общее время слияния деревьев составит <tex>O(N)</tex>.

Разбираемся с двойными дугами (на этом примере их три). Для этого мы должны выяснить, сколько начальных символов таких дуг у них совпадает. Совпадать может от одного до нескольких любое число символов, или даже все. Проверять их все по очереди нельзя (это даст квадратичное время).

Для того чтобы узнать общее начало двойной дуги, нужно взять одну чётную и одну нечётную вершину на дереве, для которых родителем является конец нашей двойной дуги. Например, на рисунке выше двойная дуга <tex>(1)</tex> (конец помечен зелёным) является общим родителем для вершин <tex>3</tex> и <tex>6</tex>. Чтобы узнать, на каком расстоянии будет расслаиваться двойная дуга, надо увеличить номера вершин на единицу и найти их родителя. Он будет находиться на единицу ближе к корню (и путь у вершин будет одинаковой строкой, не считая размера). Родитель вершин <tex>4</tex> и <tex>7</tex> помечен жёлтым, он находится на расстоянии <tex>1</tex> от корня, следовательно, дуга <tex>(1)</tex> должна расслаиваться в двух символах от корня, то есть обе дуги совпадают и их просто надо слить.

# расслоение находится на расстоянии два <tex>2</tex> от корня, то есть дуга не расслаивается.