Изменения

Перейти к: навигация, поиск

Алгоритм Укконена

20 байт убрано, 09:01, 14 апреля 2015
Алгоритм за O(n3)
Рассмотрим сначала наивный метод, который строит дерево за время <tex>O(n^3)</tex>, где <tex>n</tex> — длина исходной строки <tex>s</tex>. В дальнейшем данный алгоритм будет оптимизирован таким образом, что будет достигнута линейная скорость работы.
{{Определение
|definition= '''Неявное суффиксное дерево''' (англ. ''implicit suffix tree, IST'') строки <tex>S</tex> {{---}} это суффиксное дерево, построенное для строки <tex>S</tex> без добавления защитного символа<tex>\$</tex>.}}
[[Файл: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>
275
правок

Навигация