Изменения

[[Файл:RightMergingSS.png|thumb|right|Суффиксное дерево для строки <tex>aabcabd</tex>]]

Построим Суффиксное дерево при помощи [[Алгоритм Укконена|Алгоритма Укконена]]. При создании ответвления будем увеличивать счётчик вершины, от которой идёт новый лист, на 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>), мы получим набор подстрок, ветвящихся влево. Найдя максимальную общую подстроку двух наборов мы выполним задачу.

==См. также==