Изменения

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

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

26 байт добавлено, 23:39, 28 мая 2014
Нет описания правки
Оценим количество переходов по ребрам при поиске конца суффикса. Переход до ближайшей внутренней вершины уменьшает высоту на 1. Переход по суффиксной ссылке уменьшает высоту не более чем на 1 (по Лемме 4). Значит в течение одной фазы вверх мы переходим не более <tex> 2i </tex> раз. Но внутри одной фазы начальная глубина не меньше конечной (так как длины суффиксов убывают до 1), поэтому вниз мы могли пройти не более <tex> 2i </tex> ребер. Итого получаем оценку <tex> 4i </tex>
}}
 
== Псевдокод ==
== Итоговая линейная оценка ==
299
правок

Навигация