Изменения

== Первая версия алгоритма ==

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

=== Описание ===

Алгоритм делится на <tex>n</tex> фаз. В фазе с номером <tex>j</tex> в дерево добавляются все суффиксы подстроки <tex>s[1..j]</tex>. При добавлении суффикса <tex>s[i..j]</tex> алгоритм сначала находит конец пути из корня, помеченного подстрокой <tex>s[i..j-1]</tex>, затем добавляет к найденной вершине новое ребро с листом <tex>s_{j}</tex>, если этот символ не был добавлен ранее.