Ахо-Корасик

Бор

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

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

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

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

Реализация

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

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

const int k = 26;

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

Vertex *root = new Vertex();