333
правки
Изменения
Бор
,→Поиск строки в бору
Поиск строки <tex>S</tex> в бору: начинаем в корне, идем по ребрам, отмеченным символами <tex>S</tex>, пока возможно.
Если с последним символом <tex>S</tex> мы приходим в вершину с сохраненным идентификатором, то <tex>S</tex> — слово из словаря.
Если в какой-то момент ребра, отмеченного нужным символом, не находится, то строки <tex>S </tex> в словаре нет.
Ясно, что это занимает <tex>O (|S|)</tex> времени. Таким образом, бор — это эффективный способ хранить словарь и искать в нем слова.
