Изменения

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

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

538 байт убрано, 23:38, 28 мая 2014
→‎Первая версия алгоритма
=== Описание ===
Алгоритм делится на <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>, если этот символ не был добавлен ранее.
 
=== Псевдокод ===
Приведенный алгоритм можно записать с помощью псевдокода:
'''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_{i..j}</tex>)
Поскольку операция insert может занимать линейное время, очевидно, что время работы данного алгоритма составляет <tex>O(n^3)</tex>.
== Возможные исходы операции insert ==
Kamigan4eg
299
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/37350»

Навигация