Ахо-Корасик

Пусть дан набор строк $s_1,s_2,\dots ,s_m$ алфавита размера $k$ суммарной длины $n$, называемый словарем, и длинный текст $t$. Необходимо определить, есть ли в тексте хотя бы одно слово из словаря, и если есть, то на какой позиции

Построение дерева

Пусть у нас есть бор — дерево с корнем в некоторой вершине $root$, причём каждое ребро дерева подписано некоторой буквой. При этом, все рёбра, исходящие из некоторой вершины $x$, должны иметь разные метки

Рассмотрим в боре любой путь из корня; выпишем подряд метки рёбер этого пути. В результате мы получим некоторую строку, которая соответствует этому пути. Если же мы рассмотрим любую вершину бора, то ей поставим в соответствие строку, соответствующую пути из корня до этой вершины.

Каждая вершина бора также имеет флаг isTerminal, который равен true, если в этой вершине оканчивается какая-либо строка из словаря.

Мы можем хранить бор в виде массива $t$ структур $vertex$. Структура $vertex$ содержит флаг isTerminal, и рёбра в виде массива $next$, где $next[i]$ — указатель на вершину, в которую ведёт ребро по символу $i$, или $-1$, если такого ребра нет

Вначале бор состоит только из одной вершины — корня, а далее будем добавлять в него строки

Добавление в бор заданной строки $s$

1. Встаём в корень бора, смотрим, есть ли из корня переход по букве $s[0]$
   • Если переход есть, то переходим по нему в другую вершину
   • Иначе создаём новую вершину и добавляем переход в эту вершину по букве $s[0]$
2. Затем, стоя в какой-то вершине, повторяем процесс для букв $s[1],s[2],\dots$
3. После окончания процесса помечаем последнюю посещённую вершину, как терминальную

Пример. Пусть у нас есть словарь $S=\{he,hers,she,his\}$, тогда бор для него будет выглядеть так

Суффиксные и автоматные ссылки

Обозначим за $[u]$ слово, приводящее в вершину $u$ в боре

Определение. Суффиксная ссылка $\pi (u)=v$, если $[v]$ — максимальный суффикс $[u]$, который одновременно является префиксом какого-то слова из словаря, при этом $[v]\ne [u]$

Определение. Автоматный переход $\delta (v,c)$ ведёт в вершину, соответствующую максимальному принимаемому бором суффиксу строки $v+c$.

Построение суффиксных ссылок

Суффиксная ссылка для каждой вершины $u$ — это вершина, в которой оканчивается наидлиннейший собственный суффикс строки, соответствующей вершине $u$. Единственный особый случай — корень бора: для удобства суффиксную ссылку из него проведём в себя же.

Например, для вершины $5$ с соответствующей ей строкой $she$ максимальным подходящим суффиксом является строка $he$. Видим, что такая строка заканчивается в вершине $2$. Следовательно суффиксной ссылкой вершины для $5$ является вершина $2$

Вычисление автоматных ссылок

Автоматные ссылки вычисляются с использованием суффиксных ссылок и обычных переходов. Алгоритм строит автоматные ссылки по следующей логике:

1. Мы стоим в некоторой вершине $v$ и хотим перейти по символу $c$, тогда
   • Если есть обычный переход по символу $c$, то автоматная ссылка просто указывает на этот переход: v->autLink[c] = &v->next[c]
   • Если из вершины $v$ нет перехода по $c$, то автоматная ссылка переходит по суффиксной ссылке (если ее нет, то автомат идет в корень)
     • Смотрим, есть ли переход по символу $c$ из вершины, в которую мы попали
     • Если да, то автоматная ссылка указывает на вершину, в которую мы попадем, сделав переход по $c$
     • Если нет, то снова пытаемся пройти по суффиксной ссылке, повторяя алгоритм, пока не попадем либо в корень, либо к нужному ребру
   • Если текущая вершина — корень, то автоматная ссылка замыкается на сам корень, то есть: v->autLink[c] = v
   • Если это не корень, то автоматная ссылка указывает на результат перехода по суффиксной ссылке: v->autLink[c] = v->sufLink->autLink[c]

Работа автоматных ссылок и зачем они нужны

Предположим, что мы находимся в вершине $v$ и хотим обработать символ $c$. Если в текущей вершине $v$ есть переход по символу $c$, то мы идем по обычному переходу (ребру), и всё продолжается как обычно.

Фактически, автоматная ссылка — это резервный переход в другую вершину, где мы можем продолжить поиск.

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

После построения автоматных ссылок мы можем переходить по ним за $O(1)$

Сложность

Пусть у нас есть словарь $s_1,s_2,\dots ,s_n$

Построение бора, суффиксных ссылок и автомата займет $O(m)$, где $m={\displaystyle \sum _{i=1}^n|s_i|}$

1. В боре каждая вершина соответствует одному символу из набора строк. Значит, мы добавляем каждый символ всех строк в бор один раз
2. Суффиксные ссылки для каждой вершины бора строятся с помощью BFS. Для каждой вершины мы проверяем её суффиксную ссылку, а это делается за $O(m)$, так как каждая вершина обрабатывается один раз
3. Автоматные ссылки тоже строятся в процессе обхода бора по тому же принципу, что и суффиксные ссылки. Для каждой вершины выполняется один проход по суффиксной ссылке и проверяются символы, что снова занимает $O(m)$ времени (построение)