Изменения

Так как лист навсегда останется листом, зададим можно задать метку ребра ведущего в этот лист как <tex>s[j..x]</tex>, где <tex>x</tex> {{---}} ссылка на переменную, хранящую конец текущей подстроки. На следующих итерациях к этому ребру может применяться правило ответвления, но при этом будет меняться только левый(начальный) индекс <tex>j</tex>. Таким образом мы сможем удлинять все суффиксы, заканчивающиеся в листах за <tex>O(1)</tex>.

Будем называть самым длинным не уникальным суффиксом суффикс, который заканчиватся Таким образом на ребре и имеет максимальную длину среди всех таких суффиксов. Заметимкаждой фазе <tex>i</tex> алгоритм реально работает с суффиксами в диапазоне от <tex>j^*</tex> до <tex>k, что так как суффиксы\ k \leqslant i</tex>, продленные по второму правилу, заканчиваются в листах и далее будут продляться за а не от <tex>O(1)</tex>до <tex>i</tex>. Действительно, то на очередной итерации мы можем начинать продлять суффиксы не с если суффикс <tex>s[1j..i-12]</tex>, а с самого длинного не уникального был продлён до суффикса <tex>s[j^*..i-1]</tex>, т.е. суффикса на котором мы остановились на прошлой итерациифазе по правилу 1, применив пустое правило продлениято он и дальше будет продлеваться по правилу 1 (о чём говорит [[#l1 | лемма]]). СледовательноЕсли он был продлён по правилу 2, то была создана новая листовая вершина, значит, храня ссылку на место остановки текущей фазе <tex> i </tex> этот суффикс будет продлён до суффикса <tex>s[j..i]</tex> по листовой вершине. Поэтому после применения правила 3 на предыдущей итерации, мы можем не спускаться от корня к концу суффиксе <tex>s[j^*k..i-1]</tex> суффиксатекущую фазу можно завершить, а следующую начать сразу продлевать его символом с <tex>s_ij^* = k</tex>.

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