313
правок
Изменения
Бор
,→Построение
Это занимает, очевидно, <tex>O (|P_1| + \ldots + |P_k|) = O (n)</tex> времени.
Бор позволяет решать задачу поиска подстроки в строке, если построить его на множестве суффиксов исходной строки. Такой бор называется [[Суффиксный бор | суффиксным бором]], который позволяет найти количество различных подстрок данной строки и решить другие задачи за линейное время, если его оптимизировать. Такая оптимизация называется [[Сжатое суффиксное дерево | сжатым суффиксным деревом]].
==Поиск строки в бору==
