Изменения

Допустим, что строка ветвится влево. Пусть существуют подстроки <tex>сscs</tex> и <tex>ds</tex>. В суффиксном дереве существует вершина , тогда есть два суффикса, начинающиеся с <tex>vs</tex> соответствующая строке , которым соответствуют различные листовые вершины с различными левыми символами (<tex>sc</tex> (так как есть как минимум два суффикса, начинающиеся со строки и <tex>sd</tex>). Так же у вершины Также в дереве существует внутренняя вершина <tex>v</tex>, есть как минимум два ребёнка, у которых ''левый символ'' соответствующая строке <tex>c</tex> и <tex>ds</tex>, значит вершина по определению получаем, что <tex>v</tex> ''различна влево'' по определению.

Чтобы найти строки, ветвящиеся влево, нужно проверить все вершины суффиксного дерева на различность влево. Если какая-то вершина <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> {{---}} вершина , что она различна влево.

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