275
правок
Изменения
→Возможные исходы операции insert
Алгоритм состоит из <tex>n</tex> итераций так как в исходном тексте <tex>O(n)</tex> суффиксов, где <tex>n</tex> {{---}} длина текста. На каждой фазе происходит перебор всех суффиксов префиксов, что требует <tex>O(n^2)</tex> времени. Следовательно, общая асимптотика алгоритма <tex>O(n^3)</tex>.
== Возможные исходы операции insert Продление суффиксов ==Ниже приведены три возможных случаявозможные случаи, которые могут возникнуть при добавлении подстроки символа <tex>s_{i}</tex> ко всем суффиксам префикса <tex>s[i1..ji-1]</tex> в дерево.
{| border="1" cellpadding="5" cellspacing="0" style="text-align:center" width=70%
!style="background:#f2f2f2"|Случай
|-
|style="background:#ffffff"|''1. Продление листа''
|style="background:#ffffff"|Пусть подстрока суффикс <tex>s[ik..ji-1]</tex> кончается заканчивается в листе. Добавим элемент <tex>s_{ji}</tex> в конец последнего ребраподстроки, которой помечено ребро, ведущее в этот лист.
|style="background:#ffffff"|[[Файл:Case2.png]]
|-
|style="background:#ffffff"|''2. Создание листа''
|style="background:#ffffff"|Пусть подстрока суффикс <tex>s[ik..ji-1]</tex> кончается заканчивается в вершине, не являющейся листом, из которой нет пути по символу <tex>s_{ji}</tex>. Создадим новую дугу с началом в элементе <tex>s[ji-1]</tex> и листом <tex>s_{ji}</tex>.
|style="background:#ffffff"|[[Файл:Case1.png]]
|-
|style="background:#ffffff"|''3. Ничего не делать''
|style="background:#ffffff"|Пусть подстрока суффикс <tex>s[ik..ji-1]</tex> кончается заканчивается в вершине, из которой есть путь по <tex>s_{ji}</tex>. Тогда ничего делать не надо.
|style="background:#ffffff"|[[Файл:Case3.png]]
|}
