Изменения

'''Бор''' (trie, луч, нагруженное дерево) — структура данных для хранения набора строк, представляющая из себя подвешенное дерево с символами на ребрах. Строки получаются прохождением из корня по рёбрам, записывая соответствующие им символы, до терминальной вершины. Размер бора линейно

зависит от суммы длин всех строк, а поиск в бору занимает время, пропорциональное длине образца.

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

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

Это занимает, очевидно, <tex>O (|P_1| + ... + |P_k|) = O (n)</tex> времени.

==Поиск строки в бору==