Алгоритм Ахо-Корасик

Эта статья находится в разработке!

Задача алгоритма

Найти для каждого образца из заданного множества образцов все его вхождения в текст за время [math]O(m+n+a)[/math], где [math]m[/math] - суммарная длина образцов, [math]n[/math] - длина текста, [math]a[/math] - размер ответа (количество пар). В худшем случае [math]a=nk[/math], но он случается редко.

Шаг 1

Строим бор из образцов. См. Бор.
Построение выполняется за время [math]O(m)[/math], где [math]m[/math] - суммарная длина образцов.

Шаг 2

Превращаем бор в автомат.
Узлы бора становятся состояниями автомата; корень - начальное состояние.
Узлы бора, в которых заканчиваются образцы, становятся терминалами.

Для переходов по автомату заведём в узлах несколько функций:
1) [math]parent(u)[/math] - возвращает родителя вершины [math]u[/math];
2) [math]\pi(u) = \delta(\pi(parent(u)), c)[/math] - суффиксная ссылка; здесь [math]u[/math] - сын [math]parent(u)[/math] по символу [math]c[/math];
3) [math]\delta(u, c) = \begin{cases} v\text{, if $v$ is son by symbol $c$ in trie;}\\ \delta(\pi(u), c)\text{, else.} \end{cases}[/math] - функция перехода;
4) [math]up(u) = \begin{cases} \pi(u)\text{, if $\pi(u)$ is terminal;}\\ \emptyset\text{, if $\pi(u)$ is root;}\\ up(\pi(u))\text{, else.} \end{cases}[/math] - сжатая суффиксная ссылка.

Суффиксная ссылка [math]\pi(u) = v[/math], если [math][v][/math] - максимальный суффикс [math][u][/math], [math][v]\neq[u][/math]. Обозначение: [math][u][/math] - слово, приводящее в вершину [math]u[/math] в боре.