===Алгоритм===
Непосредственно построение:
#*Начало*'''Шаг 1.''' Начинаем с [[Дерево, эквивалентные определения | дерева]] из одной вершины (корня).#*'''Шаг 2.''' Добавляем шаблоны <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| + \ldots + |P_k|) = O(n)</tex> времени, так как поиск буквы, по которой нужно переходить, происходит за <tex>O(1)</tex>(в вершине есть указатели на буквы).
