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

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

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

Найти для каждого образца из заданного множества образцов все его вхождения в текст за время [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] - функция перехода.

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

Шаг 3

Построение сжатых суффиксных ссылок.
[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]c[/math] переходим из текущего состояния [math]u[/math] в состояние, которое вернёт функция [math]\delta(u, c)[/math]. Оказавшись в новом состоянии, отмечаем по сжатым суффиксным ссылкам образцы, которые нам встретились и их позицию (если требуется). Если новое состояние является терминалом, то соответствующие ему образцы тоже отмечаем.
Примечание. Если требуется найти только первое вхождение образца в текст, то существенно ускорить работу алгоритма могут пометки о посещённости узла, т.е. если узел посещён, то не переходить по сжатым суффиксным ссылкам. Вместо хранения пометок можно просто сбрасывать сжатую суффиксную ссылку.