76
правок
Изменения
→Добавлено новое применение
* Позволяет найти количество различных подстрок в строке за время <tex>O(|s| \log(|s|))</tex> и <tex>O(|s|)</tex> дополнительной памяти.
* Позволяет найти наименьший циклический сдвиг строки за время <tex>O(|s| \log(|s|))</tex>.
* Позволяет найти максимальную по длине строку, ветвящуюся влево и вправо за время <tex>SA + O(n)</tex>, где <tex>SA</tex> {{---}} время построения суффиксного массива.
===Поиск строки максимальной длины, ветвящейся влево и вправо===
{{Определение
|definition=
'''Строка <tex>s</tex> называется ветвящейся вправо в <tex>t</tex>''' (англ. ''right branching string''), если существуют символы <tex>c</tex> и <tex>d</tex>, такие что <tex>c</tex> <tex>\ne</tex> <tex>d</tex> : <tex>sc</tex> и <tex>sd</tex> {{---}} подстроки <tex>t</tex>. Аналогично, '''ветвящаяся влево''' (англ. ''left branching''), если <tex>cs</tex> и <tex>ds</tex> {{---}} подстроки <tex>t</tex>.
}}
==См. также==
