Изменения

Построим Первая часть алгоритма: построим Суффиксное дерево при помощи [[Алгоритм Укконена|Алгоритма Укконена]]. При создании ответвления будем увеличивать счётчик вершины, от которой идёт новый лист, на 1, если его пометка <tex>\ne</tex> <tex>\$</tex>. Таким образом, если у вершины счётчик <tex>></tex> 1, то подстрока, которую мы восстановим, идя вверх по дереву до корня, будет ветвящейся вправо (в примере для строки <tex>aabcabd</tex> это <tex>b</tex>, <tex>a</tex> и <tex>ab</tex>). Проделав аналогичную операцию Далее введём термины ''левый символ'' и ''вершина различная влево'', что бы найти строки, ветвящиеся влево.{{Определение|definition='''Левый символ''' для позиции <tex>i</tex> строки обратной исходной (<tex>reverseS</tex> - это символ <tex>S(abci-1)=cba</tex>), мы получим набор подстрок, ветвящихся влево (его элементы нужно развернуть обратно, чтобы получить исходные подстроки). Найдя пересечение двух множеств'''Левым символом''' листа <tex>L</tex> называется левый символ начала суффикса, мы получим набор строк, ветвящихся влево и вправо. Для корректности этого действия мы будем хранить номера первых символов подстроки, при пересечении будем учитывать не только содержание подстрок, но и их положение в исходной (лево- и право-ветвящаяся пара должна начинаться с одного и того же сивола). Максимальная строка последнего множества и будет ответомпредставляемого этим листом.}}{{ОпределениеТаким образом мы умеем искать строку максимальной длины|definition='''Вершина <tex>v</tex> различна влево''', ветвящуюся влево и вправо за если как минимум два листа в поддереве <tex>ST+O(N)v</tex>имеют различные ''левые символы''. По определению лист не может быть различным влево.}}

Докажем корректность алгоритма:#Предложенный алгоритм поиска строкиСтрока <tex>a</tex>, соответствующая пути к вершине <tex>v</tex>, является ветвящейся вправо корректен.#Предложенный алгоритм для перевёрнутой строки будет искать строку, ветвящуюся и влево.#Максимальный элемент пересечения предыдущих пунктов будет максимальной строкойтогда и только тогда, ветвящейся когда вершина <tex>v</tex> ''различна влево '' и вправосчётчик вершины <tex>></tex> 1.