313
правок
Изменения
Бор
,→Построение
Это занимает, очевидно, <tex>O (|P_1| + \ldots + |P_k|) = O (n)</tex> времени.
Поскольку на каждую вершину приходится <tex>O(k)</tex> памяти, то использование памяти есть <tex>O(nk)</tex>.
Потребление памяти можно уменьшить до линейного (<tex>O(n)</tex>), но за счёт увеличения асимптотики работы до <tex>O(n \log k)</tex>. Для этого достаточно хранить переходы <tex>next</tex> не массивом, а отображением <tex>map</tex><tex><</tex><tex>\mathtt{char}\ , \mathtt{int}\ </tex><tex>></tex>.
Бор позволяет решать задачу поиска подстроки в строке, если построить его на множестве суффиксов исходной строки. Такой бор называется [[Суффиксный бор | суффиксным бором]], который позволяет найти количество различных подстрок данной строки и решить другие задачи за линейное время, если его оптимизировать. Такая оптимизация называется [[Сжатое суффиксное дерево | сжатым суффиксным деревом]].
