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