Изменения

Допустим, что строка ветвится влево. Пусть существуют подстроки <tex>cs</tex> и <tex>ds</tex>, тогда есть два суффикса, начинающиеся с <tex>s</tex>, которым соответствуют различные листовые вершины с различными левыми символами (<tex>c</tex> и <tex>d</tex>). Также в дереве существует внутренняя вершина <tex>v</tex> , соответствующая строке <tex>s</tex>, по определению получаем. Из определения следует, что <tex>v</tex> различна влево.

Чтобы найти строки, ветвящиеся влево, нужно проверить все внутренние вершины суффиксного дерева на различность влево. Если какая-то вершина <tex>v</tex> будет различна влево и удовлетворять свойству ветвимости право, то строка, соответствующая вершине <tex>v</tex> будет ветвится вправо и влево.

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

Далее соберём все строки удовлетворяющие условию теоремы и найдём Теперь несложно среди них максимальную всех найденных строк найти строку максимальной длины (также этот алгоритм можно использовать для нахождения количества строк, ветвящихся влево и вправо).

Таким образом можно найти строку максимальной длины, ветвящуюся влево и вправо , за время <tex>ST+O(n)</tex>, где <tex>ST</tex> {{---}} время построения суффиксного дерева.