Изменения
→Поиск строки максимальной длины, ветвящейся влево и вправо 1.3.2
Чтобы найти строки, ветвящиеся влево, нужно проверить все вершины суффиксного дерева на различность влево. Если какая-то вершина <tex>v</tex> будет различна влево и удволетворять свойству ветвимости право, то строка, соответствующая вершине <tex>v</tex> будет ветвится вправо и влево.
Чтобы найти вершины различные влево будем хранить левый символ для каждой вершины, пусть он будет <tex>\#</tex>, если вершина различна влево. Чтобы промаркировать всё дерево, нужно записать левые символы для листов(это можно сделать при построение дерева), а затем подниматься вверх по дереву. Для каждой вершины <tex>v</tex> будем запускать проверку:*Если среди левых символов детей <tex>v</tex> есть хотя бы один <tex>\#</tex>, то запишем в <tex>v</tex> специальный символ<tex>\#</tex> и закончим проверку (в суффиксном дереве свойство различности влево наследуется вверх {{---}} строка соответствующая вершине <tex>v</tex> и строка соответствующая ребёнку <tex>v</tex> начинаются с одного и того же символа).
*Если среди левых символов детей <tex>v</tex> нет ни одного <tex>\#</tex>, то проверим на совпадение левые символы детей:
**Если все левые символ детей <tex>v</tex> одинаковы и эквивалентны <tex>x</tex>, то запишем в <tex>v</tex> этот символ <tex>x</tex>.**Если не все левые символы детей <tex>v</tex>, то запишем в <tex>v</tex> специальный символ <tex>\#</tex> {{---}} вершина различна влево.
Так как время проверки <tex>v</tex> пропорционально числу детей, время работы всего алгоритма {{---}} <tex>O(n)</tex>.
Далее соберём все строки удовлетворяющие условию теоремы и найдём среди них максимальную (так же этот алгоритм можно использовать для нахождения количества строк, ветвящихся влево и вправо).
Таким образом мы умеем искать можно найти строку максимальной длины, ветвящуюся влево и вправо за <tex>ST+O(n)</tex> (, где <tex>ST</tex> {{---}} асимптотика время построения суффиксного дерева).
==См. также==
