Изменения

Заметим что в процессе построения суффиксного дерева уже построенные суффиксные ссылки никак не изменяются. Опишем процесс построения суффиксной ссылки для новой созданной внутренней вершины. Пусть в результате очередного продления была создана новая внутренняя вершина суффикса <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>.