\Section{Суффиксный массив: продолжение}{22 апреля}{Анастасия Софронова}


\Subsection{Алгоритм Каркайнена-Сандерса ($\O(n)$)}

Хотим построить суффиксный массив за $\O(n)$, где $n = |s|$, $0 \le s_i \le \frac{3}{2}n$. Сортируем именно суффиксы, а не циклические сдвиги.

\Subsubsection{}

Допишем к строке 3 нулевых символа. Теперь сделаем новый алфавит: $(s_i, s_{i + 1}, s_{i + 2}) = w_i$. Занумеруем их от 0 до $n - 1$ с помощью цифровой сортировки наших троек.

\Subsubsection{}

$t_0: w_0w_3w_6\dots$
\\$t_1: w_1w_4w_7\dots$
\\$t_2: w_2w_5w_8\dots$

\Subsubsection{}

Запустим рекурсивно самих себя от строки $t_00t_1$. Теперь мы умеем сравнивать между собой суффиксы 0-типа и 1-типа.

\Subsubsection{}

Суффикс 2-типа = символ + номер суффикса 0-типа. Отсортируем цифровой сортировкой.

\Subsubsection{}

Осталось сделать merge двух суффиксных массивов. Мы умеем сравнивать между собой суффиксы 0-типа и 1-типа. Суффиксы 0-типа и 2-типа ~-- это первый символ и суффиксы 1-типа и 0-типа, так что мы тоже сумеем их сравнивать. Суффиксы 1-типа и 2-типа ~-- это первый символ и суффиксы 2-типа и 0-типа, их мы только что научились сравнивать. Победа.

\Subsection{Поиск строки в тексте}

$\O(|s| + \log(|text|))$.

\Subsubsection{}

Сделаем бинпоиск по суффиксному массиву, на котором уже насчитали $lcp$. Будем поддерживать $lcp$ искомой строки и границ бинпоиска. Посмотрим на строку посередине отрезка. Ясно, что $lcp(s, m) \geq max\{min\{lcp(s, l), lcp(l, m)\}, min\{lcp(s, r), lcp(r, m)\}\}$. Так что $lcp$ с m мы начинаем находить с этого максимума, а не с начала строки. $lcp(l, m) = min$ на отрезке, $lcp(r, m)$ ~-- аналогично, два других $lcp$ мы уже знаем. Пусть мы построили дерево отрезков на значениях $lcp$. Заметим, что каждый раз интересующий нас диапазон уменьшается ровно вдвое. Т.е, мы как бы всё это время спускаемся вниз по дереву отрезков. Т.е., если хранить, в какой вершине мы сейчас стоим, можем получать минимум на отрезке за $\O(1)$.

\Subsubsection{}

Далее, почему все поиски $lcp$ суммарно работают за длину строки. $lcp(s, r) + lcp(s, l)$ не уменьшаются, т.к. не уменьшается ни минимум, ни максимум из этих двух величин ($lcp(s, m)$ больше либо равен минимума, т.е. если он станет новым минимумом, то минимум не уменьшится, если новым максимумом, то аналогично). А как только мы увеличиваем $lcp(s, m)$ руками, т.е., продолжаем втупую идти с некоторого места строки, то сейчас $lcp(s, m) = max\{lcp(s, l), lcp(s, r)\}$.
