Изменения

|definition= '''Неявное суффиксное дерево''' (англ. ''implicit suffix tree, IST'') строки <tex>S</tex> {{---}} это суффиксное дерево, построенное для строки <tex>S</tex> без добавления защитного символа.}}[[Файл:ExampleUkkonen2.png|400px|thumb|right|Пример построения суффиксного дерева за <tex>O(n^3)</tex>алгоритмом Укконена.]]Пусть строка Алгоритм последовательно строит неявные суффиксные деревья для всех префиксов исходного текста <tex>S = s_1s_2s_{1}s_{2}...s_ns_{n}</tex>. Построим На <tex>i</tex>-ой итерации неявное суффиксное дерево <tex>\tau_1tau_{i-1}</tex> для префикса <tex>s_1s_{1}..s_{i-1}</tex>, после чего на каждой фазе алгоритма будем достраивать неявное суффиксное дерево достраивается до <tex>\tau_{i-}</tex> для префикса <tex>s_{1}..s_{i}</tex> подстроки . Будем спускаться от корня дерева до конца каждого суффикса префикса <tex>s_1.s_{1}..s_{i-1}</tex> до неявного суффиксного дерева и дописывать к ниму символ <tex>\tau_is_{i}</tex> подстроки . Нужно так же не забыть добавить <tex>s_1...s_{i}</tex>как уникальный суффикс, если это не было сделано ранее. Обычное суффиксное дерево можно легко получить <br> Алгоритм состоит из <tex>\tau_nn</tex> итераций так как в исходном тексте <tex>O(n)</tex>суффиксов, достроив его до где <tex>n</tex>\tau_{{---}} длина текста. На каждой фазе происходит перебор всех суффиксов префиксов, что требует <tex>O(n+1}^2)</tex>времени. Следовательно, где общая асимптотика алгоритма <tex>s_{O(n+1}=\$^3)</tex>.