Изменения

Построим Суффиксное дерево при помощи [[Алгоритм Укконена|Алгоритма Укконена]]. При создании ответвления будем увеличивать счётчик вершины, от которой идёт новый лист, на 1, если его пометка <tex>\ne</tex> <tex>\$</tex>. Таким образом, если у вершины счётчик <tex>></tex> 1, то подстрока, которую мы восстановим, идя вверх по дереву до корня, будет ветвящейся вправо (в примере для строки <tex>aabcabd</tex> это <tex>b</tex>, <tex>a</tex> и <tex>ab</tex>). Проделав аналогичную операцию для строки обратной исходной (<tex>reverse(abc)=cba</tex>), мы получим набор подстрок, ветвящихся влево(его элементы нужно развернуть обратно, чтобы получить исходные подстроки). Найдя максимальную общую подстроку пересечение двух наборов множеств, мы выполним задачуполучим набор строк, ветвящихся влево и вправо. Для корректности этого действия мы будем хранить номера первых символов подстроки, при пересечении будем учитывать не только содержание подстрок, но и их положение в исходной (лево- и право-ветвящаяся пара должна начинаться с одного и того же сивола). Максимальная строка последнего множества и будет ответом.

Таким образом мы умеем искать строку максимальной длины, ветвящуюся влево и вправо за <tex>ST+O(N)</tex>. {{Теорема|about=алгоритм корректен|statement=Пусть данный алгоритм верен. Тогда:#Предложенный алгоритм поиск строки, ветвящейся вправо корректен.#Предложенный алгоритм для перевёрнутой строки будет искать строку, ветвящуюся влево.#Максимальный элемент пересечения предыдущих пунктов будет максимальной строкой, ветвящейся влево и вправо.|proof=}}