313
правок
Изменения
Нет описания правки
Чтобы найти вершины различные влево, нужно хранить левый символ для каждой вершины или информацию о том, что она различна влево. Для поиска строки, ветвящейся влево, нужно промаркировать всё дерево. Сделать это можно при помощи [[Обход в глубину, цвета вершин| обхода в глубину]]. Начиная с корня, спускаясь вниз, для листов левый символ уже известен {{---}} при добавление нового суффикса в дерево записываем левый символ для него в лист, для вершины <tex>v</tex> запустим проверку.
:'''Случай 1.'''Если среди левых детей <tex>v</tex> есть хотя бы один, удовлетворяющий свойству различности влево, то обозначаем <tex>v</tex> как различную влево вершину (в суффиксном дереве свойство различности влево передаётся от детей к родителю {{---}} строка соответствующая вершине <tex>v</tex> и строка соответствующая ребёнку <tex>v</tex> начинаются с одного и того же символа).
:'''Случай 2.'''Если среди левых символов детей <tex>v</tex> нет ни одного со свойством различная влево вершина, то проверяем на совпадение левые символы детей.
::'''Случай 2.1.'''Если все левые символ детей <tex>v</tex> одинаковы и эквивалентны <tex>x</tex>, то записываем в <tex>v</tex> этот символ <tex>x</tex>.
::'''Случай 2.2.'''Если не все левые символы детей <tex>v</tex> эквивалентны, то записываем в <tex>v</tex>, что она различна влево.
Так как время проверки <tex>v</tex> пропорционально числу детей, время работы всего алгоритма {{---}} <tex>O(n)</tex>.
