165
правок
Изменения
→Самая длинная строка p, входящая в t дважды и не пересекаясь
==== Основные положения ====
Построим суффиксный массив строки <tex>t</tex> и посчитаем на нем [[Алгоритм_Касаи_и_др.|LCP]].
Будем говорить, что строка <tex>s</tex> соответствует каким-нибудь суффиксам <tex>i</tex> и <tex>j</tex>, если она равна максимальному префиксу этих суффиксов.
Будем говорить, что суффиксы <tex>i</tex> и <tex>j</tex> соответствуют строке <tex>s</tex>, если <tex>s</tex> входит в <tex>t</tex> дважды и не пересекаясь, а суффиксы <tex>i</tex> и <tex>j</tex> соответствуют позициям этих вхождений.
Таким образом, мы рассмотрим все строки, соответствующие условиям 1 и 2, и, следовательно, найдем ответ. Алгоритм корректный.
Заметим теперь, что искомые строки <tex>s</tex> {{---}} это префиксы суффиксов <tex>k</tex> длины <tex>lcp_klcp[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>lcp[st'] = lcp[s']</tex><br>Тогда просто обновляем <tex>i</tex> и <tex>j</tex> для вершины стека.#* <tex>lcp[st'] \geqslant lcp[s']</tex><br>В этом случае добавляем новую вершину в стек и обновляем для нее <tex>i</tex> и <tex>j</tex>.#* <tex>lcp[st'] \leqslant lcp[s']</tex><br>Достаем вершину из стека и ''пробрасываем'' значения <tex>i</tex> и <tex>j</tex> из нее в новую вершину стека. Это нужно для того, чтобы не потерять значения <tex>i</tex> и <tex>j</tex>, которые были посчитаны для строк большей длины, но так же актуальны для строк меньшей длины.
# Если в какой-то момент <tex>i</tex> и <tex>j</tex> станут удовлетворять условию 1, обновляем ответ.
