Изменения

==Построение==

Введем следующие обозначения:

*<tex>P = \{P_1,\ldots,P_k\} </tex> — набор строк, называемый словарем;

*<tex>n = \sum_{i=1}^{k|P_i|}\limits |P_i|</tex>.

Непосредственно построение:

#Начинаем с [[Дерево, эквивалентные определения | дерева]] из одной вершины (корня).

Поскольку на каждую вершину приходится <tex>O(k)</tex> памяти, то использование памяти есть <tex>O(nk)</tex>.

Бор позволяет решать задачу поиска подстроки в строке, если построить его на множестве суффиксов исходной строки.<ref>Сжатое суффиксное дерево</ref>