Изменения

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