Изменения

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