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[1..i-1]</tex> достраивается до <tex>\tau_{i}</tex> для префикса <tex>s[1..i]</tex>. Будем спускаться от корня дерева до конца каждого суффикса префикса <tex>s[1..i-1]</tex> и дописывать к ниму ним символ <tex>s_{i}</tex>. Нужно так же не забыть добавить Не стоит забывать, что <tex>s_{i}</tex> как уникальный суффиксявляется суффиксом <tex>s[1..i]</tex> , если это не было сделано ранеепоэтому его тоже нужно добавить в дерево. <br>
Алгоритм состоит из <tex>n</tex> итераций так как в исходном тексте <tex>O(n)</tex> суффиксов, где <tex>n</tex> {{---}} длина текста. На каждой фазе происходит перебор всех суффиксов префиксов, что требует <tex>O(n^2)</tex> времени. Следовательно, общая асимптотика алгоритма <tex>O(n^3)</tex>.
