76
правок
Изменения
→Поиск строки максимальной длины, ветвящейся влево и вправо v0.1
Строка <tex>s</tex> называется ветвящейся вправо в <tex>t</tex>, если существуют символы <tex>c</tex> и <tex>d</tex>, такие что <tex>c</tex> <tex>\ne</tex> <tex>d</tex> : <tex>sc</tex> и <tex>sd</tex> - подстроки <tex>t</tex>. Аналогично, ветвящаяся влево, если <tex>cs</tex> и <tex>ds</tex> - подстроки <tex>t</tex>.
}}
[[Файл: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>), мы получим набор подстрок, ветвящихся влево. Найдя максимальную общую подстроку двух наборов мы выполним задачу.
==См. также==
