Изменения

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

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

659 байт добавлено, 00:56, 6 мая 2011
Нет описания правки
При переходе по суффиксной ссылке глубина уменьшается не более чем на 1.
|proof=
Пусть мы переходим из вершины <tex> v </tex> с путевой меткой <tex>t_i ... t_j</tex> по суффиксной ссылке в вершину <tex> u </tex> с путевой меткой <tex>t_{i + 1} ... tj</tex> Определим множество <tex> A </tex> как множество вершин на пути от корня до <tex> u </tex>, исключая корень. Множество <tex> B </tex> определим как множество вершин на пути от корня до <tex> v </tex>, исключая корень. Если длина первого ребра на пути от корня до <tex> v </tex> равна единице, то выкинем из множества <tex>B</tex> вершину, в которую ведет это ребро. Итого по построению получаем: <tex></tex>
}}
Анонимный участник

Навигация