Изменения

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

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

13 байт убрано, 21:54, 28 апреля 2015
м
Использование суффиксных ссылок
=== Использование суффиксных ссылок ===
[[Файл:ExampleUkkonen7.png|300px|thumb|right|Пример использования Использование суффиксных ссылок.]]
Суффиксные ссылки используются для того, чтобы можно было быстро перейти от конца одного суффикса к концу другого, а не спускаться каждый раз от корня. Пусть мы только что продлили суффикс <tex>s[j..i-1]</tex> до суффикса <tex>s[j..i]</tex>. Теперь с помощью построенных ссылок найдем конец суффикса <tex>s[j+1..i-1]</tex>, чтобы продлить его до суффикса <tex>s[j+1..i]</tex>. Пройдем вверх по дереву до ближайшей внутренней вершины <tex>v</tex>, в которую ведет путь, помеченный <tex>s[j..r]</tex>. У вершины <tex>v</tex> есть суффиксная ссылка, так как ссылка для внутренней вершины строится внутри фазы создания этой вершины. Пусть суффиксная ссылка ведет в вершину <tex>u</tex>, которой соответствует путь с пометкой <tex>s[j+1..r]</tex>. Теперь пройдем от вершины <tex>u</tex> вниз по дереву к концу суффикса <tex>s[j+1..i-1]</tex>, и сделаем продление до суффикса <tex>s[j+1..i]</tex>.
275
правок

Навигация