Изменения
→Начало Поиск строки максимальной длины, ветвящейся влево и вправо
* Наибольшую общую подстроку двух строк
* [[Суффиксный массив| Суффиксный массив]] и массив <tex>lcp</tex> (longest common prefix) исходной строки
* Строку максимальной длины, ветвящуюся влево и вправо за <tex>ST + O(n)</tex>
===Построение суффиксного массива и массива lcp из суффиксного дерева===
Таким образом, мы умеем за <tex>O(n)</tex> строить [[Алгоритм Укконена| суффиксное дерево]], [[Алгоритм Карккайнена-Сандерса| суффиксный массив]] и преобразовывать одно в другое.
===Поиск строки максимальной длины, ветвящейся влево и вправо===
{{Определение
|definition=
Строка <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>.
}}
==См. также==
