275
правок
Изменения
→Первая версия алгоритма
|definition= '''Неявное суффиксное дерево''' строки <tex>S</tex> {{---}} это суффиксное дерево, построенное для строки <tex>S</tex> без добавления защитного символа.}}
[[Файл:ExampleUkkonen1.png|450px400px|thumb|right|Неявное и явное суффиксные деревья для строки <tex>xabxa</tex> (<tex>\$</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>, если этот символ не был добавлен ранее.
