313
правок
Изменения
Бор
,→Использование бора в качестве map
Бор позволяет решать задачу поиска подстроки в строке, если построить его на множестве суффиксов исходной строки. Такой бор называется [[Суффиксный бор | суффиксным бором]], который позволяет найти количество различных подстрок данной строки и решить другие задачи за линейное время, если его оптимизировать. Такая оптимизация называется [[Сжатое суффиксное дерево | сжатым суффиксным деревом]].
==Использование бора в качестве ''map''==Мы можем ввести для каждой вершины поле <tex>value</tex>. Например, мы имеем <tex>map<string, value></tex>. Будем искать ключ, спускаясь по бору. Соответственно, если на какой-то вершине нет пометки, что вершина является концом слова, то объекта в <tex>map</tex> нет. Если хотим добавить его, то ставим в вершину флаг конца слова и заносим значение.Работать такой алгоритм будет за <tex>O(n)</tex>, где <tex>n</tex> - количество добавленных слов.
==См. также==
