Изменения

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

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

100 байт добавлено, 21:22, 29 апреля 2015
м
Суффиксные ссылки
|statement=
Для любой внутренней вершины <tex>v</tex> суффиксного дерева существует суффиксная ссылка, ведущая в некоторую внутреннюю вершину <tex>u</tex>.
[[Файл:ExampleUkkonen8.png|400px|thumb|center|Пример суффиксных ссылок.]]
|proof=
Рассмотрим внутренную вершину <tex>v</tex> с путевой меткой <tex>s[j..i]</tex>. Так как эта вершина внутренняя, ее путевая метка ветвится справа в исходной строке. Тогда очевидно подстрока <tex>s[j+1..i]</tex> тоже ветвится справа в исходной строке, и ей соответствует некоторая внутренняя вершина <tex>u</tex>. По определению суффиксная ссылка вершины <tex>v </tex> ведет в <tex> u</tex>
275
правок

Навигация