Алгоритм Ахо-Корасик
Автомат Ахо-Корасик позволяет находить в тексте вхождения любой строки из заданного набора строк.
Автомат строится на основе бора. Каждая вершина в боре соответствует некоторой строке. Терминальные вершины соответствуют строкам из исходного набора.
Суффиксная ссылка из вершины, соответствующей строке 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.
class Trie {
struct Vertex {
bool isTerminal = false;
map<char, Vertex> next;
Vertex *sufLink = nullptr;
map<char, Vertex *> autLink;
} root;
public:
void add(const string &s) {
Vertex *v = &root;
for (const char &c : s)
v = &v->next[c];
v->isTerminal = true;
}
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 (const char &c : s) {
v = v->autLink[c];
if (v->isTerminal)
return true;
}
return false;
}
};
Ссылки
Теория:
- e-maxx.ru — Алгоритм Ахо-Корасик
- neerc.ifmo.ru/wiki — Алгоритм Ахо-Корасик
- Codeforces — Алгоритм Ахо-Корасик. Построение
- Algorithmica — Алгоритм Ахо-Корасик: 1, 2
Код: