299
правок
Изменения
→Первая версия алгоритма
=== Описание ===
Алгоритм делится на <tex>n</tex> фаз. В фазе с номером <tex>ij</tex> в дерево добавляются все суффиксы подстроки <tex>s_{1..ij}</tex>. При добавлении суффикса <tex>s_{ji..ij}</tex> алгоритм сначала находит конец пути из корня, помеченного подстрокой <tex>s_{ji..ij-1}</tex>, затем добавляет к найденной вершине новое ребро с листом <tex>s_is_j</tex>, если этот символ не был добавлен ранее.
=== Псевдокод ===
'''for''' <tex> i \leftarrow 1 </tex> '''to''' <tex> n </tex> '''do'''
'''for''' <tex> j \leftarrow 1 </tex> '''to''' <tex> i </tex> '''do'''
insert(<tex>s_{ji..ij}</tex>)
Поскольку операция insert может занимать линейное время, очевидно, что время работы данного алгоритма составляет <tex>O(n^3)</tex>.
