165
правок
Изменения
→Самая длинная строка p, входящая в t дважды и не пересекаясь
Поиск самой длинной строки <tex>p</tex>, входящей в строку <tex>t</tex> дважды и не пересекаясь за <tex>SA + O(n)</tex>
Построим суфмас строки <tex>t</tex> и посчитаем на нем LCP алгоритмом [[Алгоритм_Касаи_и_др.|Касаи, Аримуры, Арикавы, Ли, Парка]].
Рассмотрим какие-нибудь суффиксы <tex>i</tex> и <tex>j</tex> строки <tex>t</tex>. Обозначим их позиции в суфмасе за <tex>i'</tex> и <tex>j'</tex>, причем <tex>i' \leq j'</tex>.
Т.о. строка входит в <tex>t</tex> дважды и не пересекаясь тогда и только тогда, когда она удовлетворяет условиям 1 и 2.
# Построим суффиксный массив, посчитаем на нём [[Алгоритм_Касаи_и_др.|LCP]].
# Переберем все пары <tex>i</tex> и <tex>j</tex> такие, что они удовлетворяют условиям 1 и 2 и возьмем среди них максимум по длине строки.
Этот алгоритм можно реализовать за <tex>O(n^3)</tex> или, если немного подумать, то и за <tex>O(n^2)</tex>. Однако, он не позволяет достигнуть нужной нам асимптотики.
==== Оптимальное решение ====
===== Идея =====
Чтобы достигнуть асимптотики <tex>O(n)</tex>, будем перебирать всевозможные подстроки <tex>s</tex> строки <tex>t</tex>, такие, что они входят в <tex>t</tex> дважды и удовлетворяют условию 2 при любых <tex>i</tex> и <tex>j</tex>, где <tex>i</tex> и <tex>j</tex> - суффиксы, соответствующие двум любым вхождениям s в t (т.е. не обязательно непересекающимся). Для каждой такой строки <tex>s</tex> попробуем найти <tex>i</tex> и <tex>j</tex>, удовлетворяющие условию 1. Таким образом, мы рассмотрим все строки, соответствующие условиям 1 и 2, и, следовательно, найдем ответ. Алгоритм корректный.
Заметим теперь, что искомые строки <tex>s</tex> {{---}} это префиксы суффиксов <tex>k</tex> длины <tex>lcp_k</tex>.
Для того, чтобы найти для каждой такой строки <tex>s</tex> суффиксы <tex>i</tex> и <tex>j</tex>, удовлетворяющие условию 1, воспользуемся стеком
# Будем идти по суффиксному массиву в порядке лексикографической сортировки суффиксов. В стеке будем хранить префиксы уже рассмотренных суффиксов <tex>k</tex> длины <tex>lcp_k</tex> (т.е. строки <tex>s</tex>) в порядке увеличения длины. Для каждой строки из стека также будем хранить минимальный по длине суффикс <tex>i</tex> и максимальный по длине <tex>j</tex>. Обозначим за <tex>st</tex> вершину стека, а за <tex>s</tex> {{---}} текущий рассматриваемый суффикс.
# Возможны три случая:
# Если в какой-то момент <tex>i</tex> и <tex>j</tex> станут удовлетворять условию 1, обновляем ответ: '''if''' (<tex>len_s > len_{ans}</tex>) '''then''' <tex>s = ans</tex>;
===== Оценка времени работы =====
Т.к. для каждого суффикса мы выполняем <tex>O(1)</tex> операций, то итоговое время работы <tex>O(n)</tex>
