Ахо - Корасик

Дан набор образцов $p_1, \ldots, p_M$ и текст $t$. Надо найти вхождения всех образцов.

Запускать поиск подстроки по очереди - это $O(M \lvert t \rvert)$: при $M = 5000$ и тексте в миллион символов уже $5 \cdot 10^9$.

Ахо - Корасик делает это за один проход: $O(\lvert t \rvert)$ после построения.

Из чего он собран

Основа - бор всех образцов. Каждая вершина отвечает какому-то префиксу какого-то образца.

К бору добавляется суффиксная ссылка: из вершины, отвечающей строке $v$, она ведёт в вершину наибольшего собственного суффикса $v$, который тоже есть в боре.

Это ровно то же, что префикс-функция, только не на одной строке, а на дереве: там мы откатывались к наибольшему бордеру, здесь - к наибольшему суффиксу, который остался в наборе.

Автомат вместо откатов

Откатываться по ссылкам во время чтения текста можно, но неудобно. Проще сразу достроить бор до полного автомата: для каждой вершины и каждой буквы задать, куда идти.

Правило одно: если ребро есть - идём по нему; если нет - идём туда, куда пошла бы суффиксная ссылка.

queue<int> q;
q.push(0);
while (!q.empty()) {
    int v = q.front(); q.pop();
    for (int c = 0; c < K; c++) {
        int u = go[v][c];
        if (u == -1) {
            go[v][c] = (v == 0) ? 0 : go[link[v]][c];
        } else {
            link[u] = (v == 0) ? 0 : go[link[v]][c];
            q.push(u);
        }
    }
}

Обход в ширину здесь обязателен: чтобы посчитать ссылку вершины, нужна уже готовая ссылка её родителя, а родитель лежит на уровень выше.

После этого чтение текста - одна строка:

int cur = 0;
for (char ch : t) cur = go[cur][ch - 'a'];

Как получить ответы

Пока читаем текст, отмечаем в каждой посещённой вершине единицу. В конце протаскиваем счётчики по суффиксным ссылкам - в обратном порядке обхода в ширину:

for (int i = (int)order.size() - 1; i > 0; i--) {
    int v = order[i];
    visits[link[v]] += visits[v];
}

Тогда visits[конец образца] - это число вхождений образца в текст.

Почему так: вершина $v$ означает, что в этой позиции текста кончился префикс $v$; значит, кончились и все его суффиксы, которые есть в боре, - а это в точности цепочка суффиксных ссылок. Обратный порядок обхода гарантирует, что к моменту обработки $v$ её собственный счётчик уже окончателен.

Проверено: на 2000 наборах коротких образцов счётчики вхождений совпали с прямым поиском каждого образца по отдельности.

Если нужны позиции, а не количества

Тогда протаскивание не годится: надо в каждой позиции текста перебрать всю цепочку суффиксных ссылок, ведущих в терминальные вершины. Заводят сжатую терминальную ссылку - ближайший терминал вверх по цепочке:

exit[v] = terminal[link[v]] ? link[v] : exit[link[v]];

Худший случай тут неизбежно квадратичный по выводу: у текста aaaa… и образцов a, aa, aaa, … вхождений просто очень много. Асимптотика становится $O(\lvert t \rvert + \text{число вхождений})$, и это оптимально.

Сколько это стоит

Вершин в боре не больше суммарной длины образцов плюс единица. Переходов - вершины на размер алфавита, и это обычно и есть узкое место по памяти.

Измерено на наборах суммарной длины $10^5$ со словами до 30 символов:

алфавит	слов	вершин бора	память на переходы
2	5345	43 980	4,4 МБ
4	5878	68 957	6,8 МБ
26	6234	87 275	8,7 МБ

Видно главное: чем меньше алфавит, тем меньше вершин при той же суммарной длине. Это может показаться странным - кажется, что узкий алфавит должен давать длинное дерево. На деле наоборот: при двух буквах слова неизбежно делят между собой длинные общие начала, и бор сжимается. При 26 буквах случайные слова расходятся уже на второй-третьей букве, и вершин почти столько же, сколько символов.

Скорость на том же наборе: текст из $10^6$ букв четырёхбуквенного алфавита, 5852 слова, 68 939 вершин. Построение автомата - 122 мс, проход по тексту со счётчиками - 51 мс.

Для сравнения, наивный поиск каждого слова по отдельности встроенным поиском подстроки: 251 мс на первых 200 словах, то есть около 7,3 с на все. Разница примерно в сорок раз, и она растёт линейно с числом слов.

Когда он не нужен

Если все образцы одной длины $L$, задача решается хешами в пять строк: сложить хеши образцов в множество и пройтись окном длины $L$ по тексту.

Если длин мало - скажем, все образцы короче 5 - то же самое повторяют для каждой длины.

Ахо - Корасик выигрывает, когда длин много и они разные, когда ответ нужен точный, или когда поверх автомата надо считать динамику - например, «сколько строк длины $L$ не содержат ни одного образца». Последнее хешами не делается вовсе.