Изменения

'''Строка <tex>s</tex> называется ветвящейся вправо в <tex>t</tex>''' (англ. ''right merging 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 merging''), если <tex>cs</tex> и <tex>ds</tex> {{--- }} подстроки <tex>t</tex>.

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

'''Левый символ''' для позиции <tex>i</tex> строки <tex>S</tex> {{- --}} это символ <tex>S(i-1)</tex>.'''Левым символом''' листа <tex>L</tex> называется ''левый символ '' начала суффикса, представляемого этим листомведущего в этот лист.

Строка <tex>a</tex>, соответствующая пути к вершине <tex>v</tex>, является ветвящейся вправо и влево тогда и только тогда, когда вершина <tex>v</tex> ''различна влево'' и счётчик вершины <tex>>1</tex> 1.

*Предположим, что <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>s</tex> является ветвящейся вправо и влево.*Тогда существуют подстроки <tex>csa</tex> и <tex>dsb</tex>.*В суффиксном дереве существует вершина <tex>v</tex> соответствующая строке <tex>s</tex> (так как есть как минимум два суффикса, начинающиеся со строки <tex>s</tex>).*У вершины <tex>v</tex>, есть как минимум два ребёнка, которые начинаются с символов <tex>a</tex> и <tex>b</tex> <tex>\Rightarrow</tex> счётчик вершины <tex>>2</tex> 2.*Так же у вершины <tex>v</tex>, есть как минимум два ребёнка, у которых ''левый символ'' <tex>c</tex> и <tex>d</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>\$</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(Nn)</tex>.