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

Пусть дан набор строк в алфавите размера $k$ суммарной длины $n$. Алгоритм Ахо-Корасик за $O(nk)$ времени и памяти строит бор для этого набора строк, а затем по этому бору строит автомат, который может использоваться в различных строковых задачах — например, нахождения всех вхождений каждой строки из данного набора в произвольный текст за линейное время.

Алгоритм был назван именами создателей — Альфреда Ахо и Маргарет Корасик.

Автор специализируется на компьютерной лингвистике и когда-то работал над созданием разговорного интеллекта — этот модуль назывался «Болталка», говорящая на произвольные темы.

Пусть заданы $n$ плохих слов и большой текст $t$. Нужно найти суммарное количество их вхождений в этот текст.

Эту и много других задач помогают решать суффиксные ссылки. Суффиксная ссылка для вершины $v$ — это вершина, которой соответствует наидлиннейший суффикс строки, соответствующей вершине $v$, и присутствующий в боре. Будем считать, что мы их умеем быстро находить.

Добавим все плохие слова в бор. Будем считывать строку и с помощью суффиксных ссылок поддерживать самый длинный суффикс текущей строки, который принимает бор. Тогда, для конкретной позиции, мы можем быстро посчитать, какие плохие слова на нём заканчиваются — ровно те, до которых можно дойти по суффиксным ссылкам (по определению, суффиксная ссылка ведёт в наидлиннейший суффикс, присутствующий в боре). Информацию о количестве таких слов можно посчитать заранее динамикой в графе из суффиксных ссылок.

Алгоритм Ахо-Корасик позволяет строить суффиксные ссылки для произвольного бора за $O(nk)$, где $n$ и $k$ это суммарный размер строк и размер алфавита соответственно. Его описание вынесенов в отдельную статью.

Зачем это нужно

Пусть заданы $n$ плохих слов и большой текст $t$. Нужно найти суммарное количество их вхождений в этот текст.

Добавим все плохие слова в бор, и будем считывать строку и с помощью суффиксных ссылок поддерживать самый длинный суффикс текущей строки, который принимает бор.

Тогда, для конкретной позиции, мы можем быстро посчитать, какие плохие слова на нём заканчиваются — ровно те, по которым можно дойти по суффиксным ссылкам. Информацию о количестве таких слов можно посчитать заранее динамикой в графе из суффиксных ссылок.

Помимо суффиксных ссылок, нужно найти ещё переходы, чтобы поддерживать самый длинный суффикс.

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

Заметим, что всего суффиксных ссылок нужно найти $O(n)$, а переходов — $O(nk)$. Суффиксные ссылки и переходы можно быстро найти динамикой.

Ссылки. Мы можем сделать так: пройти на символ назад, а оттуда пройти по суффиксной ссылке, и уже оттуда вызвать переход.

Переходы. Вот к нашей строке прибавился символ — нужно найти самую длинную строку. Для этого можно откатываться по суффиксным ссылкам, пока не придем в вершину, из которой данный переход есть. Рано или поздно мы либо попадем в такую вершину, либо попадем в корень. Но можно поступить лениво, и просто откатиться на одну суффиксную ссылку и взять уже посчитанный переход оттуда.

In [ ]:
const int k = 26;

struct Vertex {
    Vertex *to[k] = {0}, *go[k] = {0};
    Vertex *link = 0, *p;
    int pch;
    Vertex (int _pch, Vertex *_p) { pch = _pch, p = _p; }
};

Vertex *root = new Vertex(-1, 0);
In [ ]:
void add_string (string s) {
    Vertex *v = root;
    for (char _c : s) {
        c -= 'a';
        if (!v->to[c])
            v->to[c] = new Vertex(c, v);
        v = v->to[c];
    }
}

Нам нужно объявить две функции, которые будут ссылаться друг на друга. В интерпретируемых языках (например, в питоне) можно просто объявить две функции, а вот C++ так не умеет — нужно сначала все объявить, а потом ссылаться.

In [ ]:
Vertex* go (Vertex *v, int c);

Vertex* link (Vertex *v) {
    if (!v->link) {
        if (v == root || v->p == root) v->link = root;
        else v->link = go(link(v->p), v->pch);
    }
    return v->link;
}

Vertex* go (Vertex *v, int c) {
    if (!v->go[c]) {
        if (v->to[c]) v->go[c] = v->to[c];
        else if (v == root) v->go[c] = root;
        else v->go[c] = go(link(v), c);
    }
    return v->go[c];
}