Бор

Бор

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

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

trie
trie

Бор можно удобно использовать для разных задач: * Хранение строк — занимает гораздо меньше места, чем массив или сет строк. * Сортировка строк — по бору можно пройтись 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\) это суммарный размер строк и размер алфавита соответственно. Его описание вынесенов в отдельную статью.