Изменения

В течение работы алгоритма создается не более <tex>O(n)</tex> листов, так как в исходном тексте <tex>O(n)</tex> суффиксов. По [[Сжатое_суффиксное_дерево#Количество_вершин | лемме]] внутренних вершин в дереве меньше чем листьев, следовательно, всего вершин в получившемся дереве будет <tex>O(n)</tex>. Все суффиксы, которые заканчиваются в листах, благодаря [[#l1|первой лемме]] на каждой итерации мы увеличиваем на текущий символ по умолчанию за <tex>O(1)</tex>. Текущая фаза алгоритма идет пока мы явно не продлим все суффиксы или, по [[#l2|второй лемме]], пока не будет использовано правило продления 3. При явном продлении суффикса всегда создается новый лист, в котором он заканчивается, не сложно заметить, что этот суффикс на всех последующих итерация будет продлеваться по правилу 1(за <tex>O(1)</tex>), тогда на всех <tex>n</tex> итерациях суммарно не может быть сделано более <tex>O(n)</tex> явных и неявных продлений, то есть так же теперь мы не спускаемся от корня к концу первого суффикса на текущей итерации за <tex>O(n)</tex>, а сразу, за <tex>O(1)</tex>, начинаем его продление, тогда одна итерация в среднем одна итерация будет выполняться за <tex>O(1)</tex>. Таким образом при использовании всех приведенных эвристик, алгоритм Укконена работает за <tex>O(n)</tex>.