algorithm

Алгоритм Фараха (Фарача) построения сжатого суффиксного дерева над индексированным (полиномиальным) алфавитом.

1. Зачем оно. Про временную сложность построения. Чем лучше Укконена, Винера и т.п.
Суффиксное дерево как структура данных была введена Винером в 73 году. Им же был предложен оптимальный алгоритм построения суффиксного дерева с ассимптотикой O(n) для строк длины n над конечным алфавитом. Предложенный же Фарахом алгоритм является первым, имеющим ассимптотически оптимальное время построения O(n) для строк длины n над полиномиальным алфавитом, т.е. алфавитом мощности порядка O(n).
Задачей данной работы являлась практическая реализация алгоритма Фараха и проверка линейности ассимптотики его работы.

2. Что такое сжатое суффиксное дерево.
Рассмотрим строку S над алфавитом En. Суффиксное дерево - фундаментальная структура данных для решения задач, связанных со сравнением с образцом. Она представляет собой бор суффиксов входной строки и позволяет быстро определить наличие вхождения строк в образец, число вхождений и их позицию. Различают обычное суффиксное дерево и сжатое суффиксное дерево, в котором отсутствуют вершины с одним потомком (такие вершины схлопываются в одну, поэтому ребра представляют собой подстроки образца длиной > 1). Сжатое суффиксное дерево требует O(n) памяти для хранения.
Также, обычно предполагается, что при DFS-обходе дерева суффиксы будут пройдены в лексикографическом порядке. Это требует возможность обхода исходящих ребер любой вершины в лексикографическом порядке. Суффиксное дерево, удовлетворяющее данному условию иногда, дабы подчеркнуть это свойство, называют отсортированным. 
Далее под суффиксным деревом, если не оговорено обратное, будет подразумеваться сжатое отсортированное суффиксное дерево.

3. Подготовка данных - преобразование строки над некоторым конечным алфавитом к строке над индексированным алфавитом. Что такое индексированный алфавит.
Перед описанием алгоритма следует разобраться с входными данными. Выше было сказано о том, что алгоритм Фараха работает на строках длины n над полиномиальнымм алфавитами. Полиномиальность алфавита является одной из ключевых особенностей, позволяющих добиться линейного времени построения дерева. 
Таким образом можно рассматривать символы входной строки как числа из некоторого отрезка [0, N), где N порядка O(n), т.е. неявно предполагается, что на алфавите введено отношение порядка. В общем случае символы входной строки могут быть представлены любыми числами (раз мы говорим о реализации, то символы в любом случае имеют какую-либо числовую интерпретацию в силу специфики работы компьютеров). В таком случае необходимо применить биекцию исходного алфавита в алфафит [0, N), сохраняющую лексикографический порядок симполов в алфавите. В частности, с помощью цифровой сортировки входной строки как массива символов и заменой каждого символа на его ранг в отсортированном массиве (без учета повторяющихся символов). Полученный алфавит назовем индексированным.
В алгоритме Фараха операция индексирования подразумевается сделанной заранее за неважно какое время и в общей ассимптотике не учитывается, поэтому далее будем считать, что на вход подается строка над индексированным алфавитом.

4. Рассмотрим A, LCP и равенство LCP = Depth(LCA), алгоритм поиска lca.
Помимо входных данных, рассмотрим некоторые важные структуры и алгоритмы, которые понадобятся при описании самого алгоритма.
Наименьшим общим предком двух вершин u и v дерева является вершина p, являющаяся предком для u и v, и никакой из его потомков не является одновременно предком для u и v. Обозначается это следующим образом:
    LCA(u, v) = p
Название следует из позиции вершины в дереве как самой "нижней", являющейся предком одновременно для обеих вершин.
Наибольшим общим префиксом двух строк x, y является строка z максимальной длины, позволяющей оставаться префиксом для обеих строк. С данным понятием связано другое - наибольшая длина общего префикса, равная |z|, где z = lcp(x, y). Далее под lcp(u, v) будем подразумевать длину наибольшего общего префикса, а не сам префикс.
Каждая вершина суффиксного дерева задает некоторую подстроку исходной строки. Данная подстрока составляется из подстрок, расположенных на ребрах пути из корня дерева до данной вершины. Таким образом можно отождествлять любую вершину u со строкой s(v) пути из корня до нее.

Далее приведем несколько утверждений, которые понадобятся при описании алгоритма.
Утверждение 1. В суффиксном дереве выполнено следующее равенство:
    lcp(s(u), s(v)) = |s(lca(u, v))|

Далее, там, где это очевидно, вместо s(u) будем использовать в качестве обозначения строки саму вершину u. В таком случае формула приобретет следующий вид:
    lcp(u, v) = |lca(u, v)|.

Массивом сортировки As называется лексикографически отсортированный массив всех суффиксов строки (последовательность индексов суффиксов при DFS-обходе суффиксного дерева для данной строки). Данный массив обычно называют суффиксным, но в данном алгоритме будет использовано первое название для различия со структурой, описанной ниже. Также, несмотря на то, что сам массив As хранит индексы суффиксов, будем далее, где это очевидно, под A[i] понимать и саму строку суффикса.
LCP массивом называется массив длины n - 1, состоящий из следующих элементов:
    LCP[i] = lcp(A[i], A[i+1])
Пара массивов {A, LCP} назовем суффиксным массивом.

Утверждение 2. Имея суффиксный массив, для строки длины n, можно построить суффиксное дерево за O(n) и наоборот. 
Т.е. обе структуры являются двойственными друг другу и эквивалентными, относительно определенных преобразований с линейной ассимптотикой. Данный факт не раз понадобится нам в будущем.

Утверждение 3. В суффиксном дереве с O(n) вершинами можно произвести препроцессинг за время O(n) так, что для любой пары вершин u, v, можно вычислить lca(u, v) за константное время.
Алгоритм препроцессинга будет описан далее.

5. Алгоритм Фарах-Колтона и Бендера поиска наименьшего общего предка за O(1) с препроцессингом O(N).
В качестве реализации упомянутой операции препроцессинга был выбран алгоритм Фарах-Колтона и Бендера, который является асимптотически оптимальным, и при этом сравнительно простым.

Для начала, сведем задачу LCA к задаче RMQ. Для этого проведем DFS-обход суффиксного дерева, записывая на каждом шаге в массив DfsDepths текущую глубину (глубина считается по количеству ребер от корня дерева до текущей вершины) и в обратный ему массив DfsToNode - индекс текущей вершины. 
Помимо этого, будем запоминать в массив NodeToDfs индекс шага, на котором первый раз была встречена каждая вершина дерева. 
Таким образом после обхода будем иметь три массива, которые позволят ответить на вопрос, на какой позиции в DFS-обходе встретилась вершина u, какова ее глубина и какая вершина была текущей на i-ом шаге DFS-обхода. Теперь заметим, что наименьшим общим предком вершин u, v будет являться вершина, которая была пройдена при DFS-обходе после u, но перед v, и имела наименьшую глубину. В терминах описанных выше массивов, задача сводится к поиску индекса элемента в массиве DfsDepths на отрезке [NodeToDfs(u), NodeToDfs(v)], в котором достигается минимум. Тогда искомой вершиной является:
    lca(u, v) = DfsToNode(argmin(DfsDepths[i])), 
где i = [NodeToDfs(u), NodeToDfs(v)].

Будем теперь решать задачу RMQ в данном частном случае. Заметим, что любые два соседних элемента в массиве DfsDepths отличаются ровно на единицу - мы либо идём в потомка, увеличивая глубину, либо идём в предка, уменьшая ее. 

Построим сначала алгоритм, решающий эту задачу с препроцессингом O(N log N) и O(1) на запрос. Для этого создадим так называемую SparseTable T[l,i], где каждый элемент T[l,i] равен минимуму DfsDepths на промежутке [l; l+2i). Очевидно, 0 <= i <= |-log N-|, и потому размер SparseTable будет O(NlogN). Построить её можно за O(NlogN), если заметить, что T[l,i] = min(T[l,i-1], T[l+2i-1,i-1]). 

Тогда на запрос (l,r) ответом будет min (T[l,sz], T[r-2sz+1,sz]), где sz - наибольшая степень двойки, не превосходящая r-l+1. Т.е. мы берём отрезок (l,r) и покрываем его двумя отрезками длины 2sz - один начинающийся в l, а другой заканчивающийся в r. 
Для того, чтобы достигнуть асимптотики O(1) на запрос, мы должны предпосчитать значения sz для всех возможных длин от 1 до N.

Теперь улучшим алгоритм до асимптотики O(N).

Разобьём массив DfsDepths на блоки размером K = 0.5 log2 N. Для каждого блока посчитаем минимальный элемент в нём и его позицию. Пусть B - это массив размером N / K, составленный из этих минимумов в каждом блоке. Построим по массиву B SparseTable, как описано выше. Тогда размер SparseTable и время её построения будут равны:

    N/K logN/K = (2N / log N) log(2N / logN) = (2N / logN) (1 + log(N / logN)) <= 2N / logN + 2N = O(N)

Теперь осталось научиться быстро отвечать на запросы RMQ внутри каждого блока. В самом деле, если поступил запрос RMQ(l,r), то в случае, когда l и r находятся в разных блоках, ответом будет минимум из следующих значений: 
    минимум в блоке l - начиная с l и до конца блока
    минимум в блоках после l и до r не включительно
    минимум в блоке r - от начала блока до r. 

На запрос "минимум в блоках" мы уже можем отвечать за O (1) с помощью SparseTable, остались только запросы RMQ внутри блоков.

Здесь необходимо воспользоваться "+-1 свойством". Заметим, что, если внутри каждого блока от каждого его элемента отнять первый элемент, то все блоки будут однозначно определяться последовательностью длины K-1, состоящей из чисел +-1. Следовательно, количество возможных различных блоков будет равно:
    2^(K-1) = 2^(0.5logN - 1) = 0.5 sqrt(N)

Тогда количество различных блоков будет O(sqrt(N)), а значит можно предпосчитать результаты RMQ внутри всех различных блоков за O(sqrt(N)K^2) = O(sqrt(N) log^2 N) = O(N). С точки зрения реализации, мы можем каждый блок характеризовать битовой маской длины K-1, которая поместится в стандартный тип int, и хранить предпосчитанные RMQ в некотором массиве R[mask,l,r] размера O(sqrt(N) log^2 N).

Таким образом теперь можно в сумме за O(N) предпосчитывать результаты RMQ внутри каждого блока, а также RMQ над самими блоками и отвечать на каждый запрос RMQ за O(1), пользуясь только предвычисленными значениями.

6. Алгоритм Фараха построения суффиксного дерева. 
Данный алгоритм состоит из трех шагов: 
    * рекурсивного построения суффиксного дерева от строки длины n/2, полученной из четных пар
    * построения СД для строки длины n/2 из нечетных пар, используя СД для четных пар, 
    * слияния этих четного и нечетного СД в одно

6. Шаг.1 построения дерева (построение четного дерева):
    а) будем рассматривать пары символов (s[2i], s[2i + 1]), т.е. пары символов, начинающиеся на четных позициях. Тогда, если отсортировать их лексикографически (две цифровых сортировки), удалить дубли и вместо каждой пары взять ее ранг, то получим новую строку строку длины n/2
    б) построим ССД для полученной строки
    в) построим {A, LCP} по ССД
7. Шаг.2 построения дерева (построение нечетного дерева):
    а) будем рассматривать пары символов (s[2i + 1], s[2i + 2]), т.е. пары символов, начинающиеся на нечетных позициях. Тогда позиции пар после первой цифровой сортировки должны быть такими же как в A из 6в (поэтому вместо сортировки используем его). Далее используем цифровую сортировку для первых символов пар.
    б) A = ..., LCP = ... 
8. Шаг.3 построения дерева (слияние деревьев и последующее построение суффиксного дерева на его основе)
9. Особенности реализации алгоритма
10. Вывод