Последовательное сравнение нескольких строк: различия между версиями

Алгоритм Ахо-Корасик вначале строит [[trie|префиксное дерево]] <math>T(\mathcal{P})</math> – цифровое дерево, распознающее шаблоны <math>\mathcal{P}</math>. Префиксное дерево <math>T(\mathcal{P})</math> представляет собой дерево, ребра которого помечены буквами, а вдоль ветвей можно прочесть шаблоны <math>\mathcal{P}</math>. Вершина p префиксного дерева <math>T(\mathcal{P})</math> ассоциируется с уникальным словом w, «написанным» по пути в <math>T(\mathcal{P})</math>, ведущему из его корня в p. Сам корень идентифицируется с пустым словом <math>\varepsilon</math>. Заметим, что если w является вершиной в <math>T(\mathcal{P})</math>, то w является префиксом некоторого шаблона <math>P^i \in \mathcal{P}</math>. Если вдобавок к этому <math>a \in \Sigma</math>, то child(w, a) совпадает с wa, если wa является вершиной в <math>T(\mathcal{P})</math>, и равно NIL в противном случае.

На втором этапе, когда шаблоны добавляются к префиксному дереву, алгоритм инициализирует выходную функцию ''out''. Он ассоциирует одноэлементное множество <math>{P^i}</math> с вершинами <math>P^i (1 \le i \le k)</math> и пустое множество – со всеми другими вершинами <math>T(\mathcal{P})</math>.

Наконец, последним этапом предварительной обработки является создание ссылок для случаев несовпадения для каждой вершины и одновременное завершение создания выходной функции. Функция несовпадения ''fail'' определяется на вершинах следующим образом (w является вершиной): fail(w) = u, где u – самый длинный подходящий суффикс w, принадлежащий к <math>T(\mathcal{P})</math>. Вычисление ссылок для несовпадений выполняется в процессе обхода <math>T(\mathcal{P})</math> в ширину. Завершение выходной функции выполняется в ходе вычисления функции для несовпадения с использованием следующего правила: если <math>fail(w) = u</math>, то <math>out(w) = out(w) \cup out(u)</math>.