\Section{Алгоритм Ахо-Корасик}{24 апреля}{Севастюк Дмитрий}

\Subsection{Бор}

Вспомним, что такое бор. Бор - корневое дерево, в котором рёбра подписаны буквами. Бор нужен для хранения слов (строк) как путей от корня до листа. По умолчанию каждое ребро подписано одной буквой, но, если у какой-то вершины ровно один потомок, можно объединить идущие из неё "наверх"\ и "вниз"\ рёбра в одно, на котором будут записаны сначала буквы с первого, а потом - со второго.\\

Хранить можно, например, массивом Next[s][$\sum$], где s - длина слова, а $\sum$ - размер алфавита.

\begin{center}
	\begin{tabular}{lll}
		\textbf{Способ хранения} & \textbf{Время спуска по строке} & \textbf{Память на ребро}\\
		Array & $\O(|s|)$ & $\O(|\sum|)$ \\
		List & $\O(|s| \cdot |\sum|)$ & $\O(1)$ \\
		TreeMap & $\O(|s| \cdot |\log{\sum|})$ & $\O(1)$ \\
		HashMap & $\O(|s|)$ с большой const & $\O(1)$ \\
		SplayMap & $\O(|s| + |\log{\sum|})$ & $\O(1)$ \\
	\end{tabular}
\end{center}

\Subsection{Суффиксная ссылка}

\begin{Def} 
	Суффиксная ссылка вершины \textbf{v} - префикс-функция пути до \textbf{v}, то есть ссылка на вершину \textbf{u}, в которой оканчивается максимальный путь от корня, совпадающий с каким-то собственным суффиксом пути от корня до \textbf{v}. Если длина такого максимального пути равна нулю, то суффиксная ссылка указывает на корень.
\end{Def}

\Subsection{Алгоритм Ахо-Корасик}

Алгоритм по набору строк строит бор и считает на нём суффиксные ссылки.

\begin{quote}
	\textbf{Он делает это. Он делает это. Он делает это! Он это делает.}
\end{quote}

Бор строить уже научились, осталось посчитать суффиксные ссылки. Рассмотрим 2 способа.

\Subsubsection{Способ первый - как префикс-функция}

При подсчёте суффиксной ссылки вершины \textbf{v} будем переходить по уже посчитанной суффиксной ссылке её отца \textbf{parent[v]} и сравнивать следующий на пути в \textbf{v} символ с тем, что на ребре (\textbf{parent[v]}, \textbf{v}). Заметим, что если бы в боре была одна строка, то мы бы именно посчитали префикс-функцию от неё.\\

\pagebreak

\lstinputlisting{sevastuk/sufLinkOne.cpp}

\textbf{pch[v]} - символ на ребре (\textbf{parent[v]}, \textbf{v}).\\

Для того, чтобы не было крайнего случая, заведём фиктивную вершину \textbf{null}. Суффиксные ссылки, которые должны были вести в корень, бедут вести в \textbf{null}, а из \textbf{null} будут все рёбра, причём вести они будут в корень.\\

Когда мы искали префикс-функцию, мы говорили, что если сейчас рассматривается \textbf{i}-я позиция, то есть множество суффиксов отрезка до (\textbf{i-1})-й позиции и мы умеем его перебирать. Перебирали, находили самый длинный, к которому можно преписать символ \textbf{i}-й позиции и приписывали. Сделаем то же самое на боре.\\

\lstinputlisting{sevastuk/sufLinkOneBFS.cpp}

Онлайн сложно, но можно. Пополняемые структуры данных в помощь.\\

\begin{Thm}{Время работы}\\
	Построение работает за сумму длин строк $O(\sum\limits_{i = 1}^{n} |s_i|)$.
\end{Thm}
\begin{proof} 
	Для каждого пути от корня до листа бора алгоритм вычисления всех суффиксных ссылок на этом пути работает ровно так же, как вычисление префикс-функции на соответствующей этому пути строке. При вычислении суффиксной ссылки от вершины \textbf{v} мы переходим в \textbf{parent[v]} и берём её суффиксную ссылку, оказываемся в том же положении, в котором закончили предыдущий шаг.
\end{proof}

Важно понимать, что алгоритм работает именно за сумму длин строк, а не за размер бора. Например, может быть "веник"\ - несколько строк, различающихся только последней буквой.\\

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

\lstinputlisting{sevastuk/sufLinkOneWhile.cpp}

\begin{Lm}{Время работы}\\
	Проверка, входит ли какое-то из данных слов в текст займёт $\O(\text{построение бора} + |text|)$.
\end{Lm}
\begin{proof} 
	Глубина вершины внутри \textbf{while} убывает.
\end{proof}

Можно было дописать в начало текста ранее отсутствовавший в алфавите символ и, добавляя текст в бор, проверять, не создали ли мы суффиксную ссылку на старый лист. Но это могло бы потребовать очень много памяти.\\

Мы находим самый длинный суффикс. Но, возможно, был более короткий суффикс, являющийся словарным словом. Если некоторые словарные слова оканчиваются не в листе, то для каждой вершины нужно хранить, терминальная она или нет. Изначально как терминальные помечены те вершины, в которых заканчиваются слова. А в конец алгоритма нужно добавить \textbf{is\_terminal |= is\_terminal[suf[v]]}.

\Subsubsection{Способ второй - полный автомат}

При построении бора и при проходе по тексту мы используем один и тот же код. Дабы не копипастить, вынесем его в отдельную функцию. Эта функция будет считать, куда мы попадём, если захотим спуститься из вершины \textbf{v}. Осталось перебрать все вершины. Теперь \textbf{while} из прохода по тексту не нужен, ведь \textbf{Next[v][text[i]]} - то, где мы хотим оказаться.\\

\lstinputlisting{sevastuk/sufLinkTwo.cpp}

\begin{Lm}{Время работы и память}\\
	Время работы = память = $\O(|\text{бор}| \cdot |\sum|)$.
\end{Lm}
\begin{proof} 
	В каждой вершине выполняется $\O(1)$ действий, а потом - ещё по $\O(1)$ действий на каждый символ алфавита.
\end{proof}