275
правок
Изменения
→Алгоритм за O(n3)
[[Файл: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>O(n^2)</tex>. Но оптимизировать такой квадратичный алгоритм до линейного немного сложнее, хотя именно это и делает [[Алгоритм МакКрейта]]. Оптимизируя описанный выше алгоритм, мы получим более простой алгоритм за <tex>O(n)</tex>.
Алгоритм состоит из <tex>n</tex> итераций так как в исходном тексте <tex>O(n)</tex> суффиксов. На каждой фазе происходит продление всех суффиксов по порядку, что требует <tex>O(n^2)</tex> времени. Следовательно, общая асимптотика алгоритма <tex>O(n^3)</tex>.
