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

Описание

Автомат Ахо-Корасик позволяет находить в тексте вхождения любой строки из заданного набора строк.

Автомат строится на основе бора. Каждая вершина в боре соответствует некоторой строке. Терминальные вершины соответствуют строкам из исходного набора.

Суффиксная ссылка из вершины, соответствующей строке s, ведёт в вершину, соответствующую длиннейшему из имеющихся в боре суффиксов строки s.
Суть суффиксных ссылок та же, что и ячеек префикс-функции — они определяют, в какое состояние (в какую вершину) мы переходим, если очередной символ текста не совпал с ожидаемым (в данном случае ожидаемыми будут символы, имеющиеся в next у соответствующей вершины бора).

Чтобы за O(1) определять, в какую вершину мы должны перейти, если были в вершине v и встретили символ c, дополнительно вычисляются автоматные ссылки: v->autLink[c].

Если мы будем просматривать вершины бора в порядке обхода BFSом, то суффиксные и автоматные ссылки можно вычислять так:

• Суффиксная ссылка из вершины to при просмотре ребра v → (c, to): Если v — корень, то to->sufLink = v, иначе to->sufLink = v->sufLink->autLink[c].
• Автоматные ссылки из вершины v: Перебираем все символы алфавита. Если символ c есть в v->next, то v->autLink[c] = &v->next[c], иначе, если v — корень, то v->autLink[c] = v, иначе v->autLink[c] = v->sufLink->autLink[c].

Чтобы не пропустить вхождения строк, являющиеся суффиксами других строк (набор строк — ABA и B, текст — AB, хотим не пропустить вхождение B), нужно помечать вершину v как терминальную, если терминальной была вершина v->sufLink.

Определение позиций вхождений каждой строки

Если нужно не просто проверить, содержал ли текст хотя бы одну строку из набора, а найти позиции вхождений каждой строки, вносятся следующие изменения:

• Вместо bool isTerminal используются vector<int> termIndexes и Vertex *termLink;
• termIndexes — массив номеров исходных строк, заканчивающихся в данной вершине (если в наборе не могло быть одинаковых строк, то достаточно одного номера);
• termLink — ссылка на ближайшую вершину, отличную от данной, у которой isTerminal был бы равен true (то есть эта вершина либо сама является концом какой-то из исходных строк, либо из неё по суффиксным ссылкам достижим такой конец);
• Признаком того, что найдено вхождение какой-то из исходных строк, раньше было isTerminal == true у текущей вершины. Сейчас это будет либо !termIndexes.empty(), либо termLink != nullptr;
• Когда мы обнаруживаем вершину с вхождением, от неё нужно переходить по termLink, пока такой переход возможен, и добавлять в ответ termIndexes всех посещённых вершин.

Оптимизации

• Если не важен порядок символов, тип next и autLink можно заменить на unordered_map;
• Тип autLink можно заменить на vector или array;
• Новые вершины можно складывать в отдельный vector или list, тогда тип next можно будет заменить на map<char, int> (если вершины хранятся в vector) или map<char, Vertex *> (если вершины хранятся в list);
• Можно объединить next и autLink.

Код

class Trie { struct Vertex { bool isTerminal = 0; map<char, Vertex> next; Vertex *sufLink = 0; map<char, Vertex *> autLink; } root; public: void insert(const string &s) { Vertex *v = &root; for (char c : s) v = &v->next[c]; v->isTerminal = 1; } void build(int alphabetSize) { queue<Vertex *> q; root.sufLink = &root; q.push(&root); while (!q.empty()) { Vertex *v = q.front(); q.pop(); for (auto &[c, to] : v->next) { to.sufLink = (v == &root ? &root : v->sufLink->autLink[c]); q.push(&to); } for (char c = 'a'; c < 'a' + alphabetSize; c++) { if (v->next.count(c)) v->autLink[c] = &v->next[c]; else v->autLink[c] = (v == &root ? &root : v->sufLink->autLink[c]); } v->isTerminal |= v->sufLink->isTerminal; } } bool check(const string &s) { Vertex *v = &root; for (char c : s) { v = v->autLink[c]; if (v->isTerminal) return 1; } return 0; } };

class Trie { struct Vertex { vector<int> termIndexes; Vertex *termLink = 0; unordered_map<char, Vertex> next; Vertex *sufLink = 0; unordered_map<char, Vertex *> autLink; } root; int stringCount = 0; public: void insert(const string &s) { Vertex *v = &root; for (char c : s) v = &v->next[c]; v->termIndexes.push_back(stringCount++); } void build(int alphabetSize) { queue<Vertex *> q; root.sufLink = &root; q.push(&root); while (!q.empty()) { Vertex *v = q.front(); q.pop(); for (auto &[c, to] : v->next) { to.sufLink = (v == &root ? &root : v->sufLink->autLink[c]); q.push(&to); } for (char c = 'a'; c < 'a' + alphabetSize; c++) { if (v->next.count(c)) v->autLink[c] = &v->next[c]; else v->autLink[c] = (v == &root ? &root : v->sufLink->autLink[c]); } v->termLink = (!v->sufLink->termIndexes.empty() ? v->sufLink : v->sufLink->termLink); } } vector<vector<int>> check(const string &s) { vector<vector<int>> res(stringCount); Vertex *v = &root; for (int i = 0; i < s.size(); i++) { v = v->autLink[s[i]]; if (!v->termIndexes.empty() || v->termLink) for (Vertex *term = (!v->termIndexes.empty() ? v : v->termLink); term; term = term->termLink) for (int termIndex : term->termIndexes) res[termIndex].push_back(i); } return res; } };

Ссылки

Теория:

• e-maxx.ru — Алгоритм Ахо-Корасик
• neerc.ifmo.ru/wiki — Алгоритм Ахо-Корасик
• Codeforces — Алгоритм Ахо-Корасик. Построение
• Algorithmica — Алгоритм Ахо-Корасик: 1, 2

Код:

• Codelibrary — aho-corasick.cpp
• Algos — Aho-Corasick.cpp