275
правок
Изменения
→Минусы алгоритма Укконена
== Минусы алгоритма Укконена ==
Не смотря на то, что данный алгоритм является одном из самых простых алгоритмов для построения суффиксных деревьев и использует online подход, у него есть серьезные недостатки, из-за которых его не часто используют на практике:
# Константное время на одну итерацию {{---}} это амортизированная оценка, в худшем случае одна фаза может выполняться за <tex>O(n)</tex> времени. Например, алгоритм Дэни Бреслауера и Джузеппе Итальяно<ref>[https://books.google.ru/books?id=sGDXz53FwM4C&pglpg=PP11&lpgots=PP11utJ8jnql5h&dq=Dany+Breslauer,+Giuseppe+F%20Breslauer%2C%20Giuseppe%20F.+Italiano:+Near+Real%20Italiano%3A%20Near%20Real-Time+Suffix+Tree+Construction+via+the+Fringe+Marked+Ancestor+Problem%20Suffix%20Tree%20Construction%20via%20the%20Fringe%20Marked%20Ancestor%20Problem.&source=bl&ots=utJ8jnql5h&sig=qjCsObtl4pvkIVOSgwaYc3podxk&hl=ru&sa=X&ei=thcsVaexJ-HXyQP-vIC4BQ&vedpg=0CEMQ6AEwBQPA156#v=onepage&q&f=false Dany Breslauer, Giuseppe F. Italiano: Near Real-Time Suffix Tree Construction via the Fringe Marked Ancestor Problem.]</ref>, хоть и строит дерево за <tex>O(n \log \log n)</tex>, но на одну итерацию в худшем случае тратит <tex>O(\log \log n)</tex> времени.
== Реализация ==
