Изменения

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

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

226 байт добавлено, 22:05, 14 апреля 2015
Построение суффиксных ссылок
=== Построение суффиксных ссылок ===
Заметим что в процессе построения суффиксного дерева уже построенные суффиксные ссылки никак не изменяются. Опишем процесс построения суффиксной ссылки для новой созданной внутренней вершины. Пусть в результате очередного продления была создана новая внутренняя вершина суффикса <tex>vs[k..i-1]</tex> с путевой меткой была создана новая внутренняя вершина <tex>s[l..r]v</tex>. Не будем специально искать, куда должна указывать ссылка. Перейдем к следующему шагу текущей фазы, на котором суффикс <tex>s[jk+1..i-1]</tex> будет увеличен до суффикса <tex>s[jk+1..i]</tex>. Этот суффикс может так же оканчиваться на ребреили в уже созданной раннее внутренней вершине, в листе он, очевидно, но тогда заканчиваться не может. Тогда в первом случае будет создана новая внутренняя вершина <tex>u</tex>, в которую определению и а во втором эта вершина уже будет вести суффиксная ссылка существовать. Проведем суффиксную ссылку из вершины <tex>v</tex> в вершину <tex>u</tex>.
=== Оценка числа переходов ===
275
правок

Навигация