Изменения

Рассмотрим сначала наивный метод, который строит дерево за время <tex>O(n^3)</tex>, где <tex>n</tex> — длина исходной строки <tex>s</tex>. В дальнейшем данный алгоритм будет оптимизирован таким образом, что будет достигнута линейная скорость работы. 

Алгоритм делится на [[Файл:ExampleUkkonen2.png|400px|thumb|right|Пример построения суффиксного дерева за <tex>O(n^3)</tex> фаз. В фазе с номером ]]Пусть строка <tex>j</tex> в дерево добавляются все суффиксы подстроки <tex>s[1S = s_1s_2...j]s_n</tex>. При добавлении суффикса Построим суффиксное дерево для <tex>s[i..j]s_1</tex> алгоритм сначала находит конец пути из корня, помеченного подстрокой после чего на каждой фазе алгоритма будем достраивать суффиксное дерево подстроки <tex>s[is_1...js_{i-1]}</tex>, затем добавляет к найденной вершине новое ребро с листом до суффиксного дерева подстроки <tex>s_1...s_{ji}</tex>, если этот символ не был добавлен ранее.