313
правок
Изменения
Бор
,→Построение
#Если [[Основные определения теории графов | ребра]], отмеченного очередной буквой <tex>P_i</tex> нет, то создаем новые ребра и вершины для всех оставшихся символов <tex>P_i</tex>.
Это занимает, очевидно, <tex>O (|P_1| + \ldots + |P_k|) = O (n)</tex> времени., так как поиск буквы, по которой нужно переходить, происходит за <tex>O(1)</tex>
Поскольку на каждую вершину приходится <tex>O(k)</tex> памяти, то использование памяти есть <tex>O(nk)</tex>.
