trie.md

Бор

Префиксное дерево или бор — это структура данных для компактного хранения строк.

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

Бор можно удобно использовать для разных задач:

• Хранение строк — занимает гораздо меньше места, чем массив или сет строк.

• Сортировка строк — по бору можно пройтись dfs-ом и вывести все строки в лексикографическом порядке.

• Сет строк — как мы увидим, в нем легко добавлять и удалять слова, а также проверять, если ли слово в бореи.

Реализация

Бор состоит из ссылающихся друг на друга вершин. В вершине обычно хранится такая информация:

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

const int k = 26;

struct Vertex {
    Vertex* to[k] = {0};
    bool terminal = 0;
};

Vertex *root = new Vertex();

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

void add_string (string &s) {
    v = root;
    for (char c : s) {
        c -= 'a';
        if (!v->to[c]) 
            v->to[c] = new Vertex();
        v = v->to[c];
    }
    v->terminal = true;
}

Чтобы проверить, есть ли слово в боре, нужно пройти от корня по символам слова. Если в конце оказались в терминальной вершине — то есть. Если оказались в нетерминальной или когда-нибудь потребовалось пройтись по несуществущей ссылке — то есть.

Удалить слово можно лениво, просто дойдя до него и убрав флаг терминальности.

Как хранить ссылки

Хранить ссылки на детей не обязательно в массиве. Возможно, наш алфавит большой — у нас тогда просто не хватит памяти инициализировать столько массивов, большинство из которых будут пустыми.

В этом случае можно придумать какой-нибудь другой способ хранить отображение из символа в ссылку на вершину, например бинарном дереве (map) или хэш-таблице (unordered_map). Они будут работать дольше (но лишь в константу раз), но зато потребление памяти в них будет линейным. У map-а есть ещё одно преимущество, что он хранит ссылки уже отсортированными по символам — так можно отсортировать строки, например.

Учитывайте, что писать бор можно по-разному, особенно когда решаете задачи с жестокими ограничениями.

Суффиксные ссылки

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

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

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

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