165
правок
Изменения
→Применения
=== Поиск подстроки в строке ===
=== Подсчет LCP для лексикографически соседних лексикографически суффиксов ===
=== Количество Число различных подстрок в строке ===
Вычисление количества числа различных подстрок в строке за время <tex>O(|s| \log(|s|))</tex> и <tex>O(|s|)</tex> дополнительной памяти.
=== Максимальная по длине ветвящаяся влево и вправо строка ===
Поиск максимальной по длине строки, ветвящейся влево и вправо за время <tex>SA + O(n)</tex>.
Данная задача также может быть [[Сжатое_суффиксное_дерево#Поиск строки максимальной длины, ветвящейся влево и вправо|решена]] при помощи [[Сжатое_суффиксное_дерево|суффиксного дерева]].
=== Самая длинная строка p, входящая в t дважды и не пересекаясь ===
Тогда на ум приходит следующий наивный алгоритм:
# Построим суффиксный массив, посчитаем на нём [[Алгоритм_Касаи_и_др.|LCP]].
# Переберем все пары <tex>i</tex> и <tex>j</tex> такие, что они удовлетворяют условиям 1 и 2 и возьмем среди них максимум по длине строки.
