Бор

Введение

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

Она представляется в виде дерева, где рёбра помечены символами.

Каждая вершина соответствует строке, образованной чтением всех символов на пути от корня до этой вершины.

Корень представляет пустую строку.

Построение дерева

Изначально бор состоит из одной вершины: корня.

Пусть edge(x, g) обозначает вершину, достижимую из вершины x при переходе по ребру, помеченному символом g.

Добавление строки

Предположим, мы хотим добавить строку $S$ длины $m$.

Мы начинаем с корня:

• пусть x = root

Затем для каждого символа S[i]:

• если ребро edge(x, S[i]) уже существует, мы переходим по нему;
• иначе мы создаём новую вершину, добавляем соответствующее ребро и затем переходим по нему.

В конце конечная вершина представляет всю строку $S$. Мы помечаем эту вершину как терминальную.

Поиск строки

Чтобы найти строку $S$, мы начинаем от корня и последовательно переходим по рёбрам, соответствующим её символам, один за другим.