Изменения

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