Изменения

'''Строка <tex>s</tex> называется ветвящейся вправо в <tex>t</tex>''' (англ. ''right merging branching string''), если существуют символы <tex>c</tex> и <tex>d</tex>, такие что <tex>c</tex> <tex>\ne</tex> <tex>d</tex> : <tex>sc</tex> и <tex>sd</tex> {{---}} подстроки <tex>t</tex>. Аналогично, '''ветвящаяся влево''' (англ. ''left mergingbranching''), если <tex>cs</tex> и <tex>ds</tex> {{---}} подстроки <tex>t</tex>.

[[Файл:RightMergingSS.png|thumb|400px|center|Суффиксное дерево для строки <tex>aabcabd</tex>]]Построим cуффиксное дерево при помощи [[Алгоритм Укконена|Алгоритма Укконена]]. В полученном дереве не листовой вершине <tex>v</tex> будет соответствовать подстрока <tex>s</tex>, которая ветвится вправо, при условии, что количество "хороших" детей вершины <tex>v > 2</tex> ("хорошие" дети {{- --}} листы, метка которых <tex>\ne\$</tex>). В примере для строки <tex>aabcabd</tex> это <tex>b</tex>, <tex>a</tex> и <tex>ab</tex>. Далее введём термины ''левый символ'' и ''вершина различная влево'', что бы чтобы найти строки, ветвящиеся влево.

Предположим, что <tex>v</tex> различна влево. Значит, что существуют подстроки <tex>cs</tex> и <tex>ds</tex>. Пусть за первой подстрокой следует символ <tex>p</tex>. Если за второй подстрокой следует символ, <tex>\ne p</tex>, то <tex>s</tex> {{- --}} строка, ветвящаяся вправо и влево. Так как у <tex>v</tex> есть два различных ребёнка, которые начинаются с различных символов <tex>p,q \ne \$</tex>, строка является ветвящейся вправо.

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

Что бы Чтобы найти вершины различные влево будем хранить левый символ для каждой вершины, пусть он будет <tex>\$</tex>, если вершина различна влево. Что бы Чтобы промаркировать всё дерево, нужно записать левые символы для листов, а затем подниматься вверх по дереву. Для каждой вершины <tex>v</tex> будем запускать проверку:

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