313
правок
Изменения
Бор
,→Построение
Пусть <tex>n = \sum_{i=1}^k|P_i|</tex>.
Непосредственно построение:#Начинаем с дерева из одной вершины (корня); добавляем .#Добавляем шаблоны <tex>P_i</tex> один за другим:.#Следуем из корня по ребрам, отмеченным буквами из <tex>P_i</tex>, пока возможно. #Если <tex>P_i</tex> заканчивается в <tex>v</tex>, сохраняем идентификатор <tex>P_i</tex> (например, <tex>i</tex>) в <tex>v</tex> и отмечаем вершину <tex>v</tex> как терминальную. #Если ребра, отмеченного очередной буквой <tex>P_i</tex> нет, то создаем новые ребра и вершины для всех оставшихся символов <tex>P_i</tex>.
Это занимает, очевидно, <tex>O (|P_1| + ... + |P_k|) = O (n)</tex> времени.