165
правок
Изменения
м
Чтобы достигнуть асимптотики <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> {{---}} суффиксы, соответствующие двум любым вхождениям <tex>s</tex> в <tex>t</tex> (т.е. не обязательно непересекающимся).Для каждой такой строки <tex>s</tex> попробуем найти <tex>i</tex> и <tex>j</tex>, удовлетворяющие условию 1.
→Самая длинная строка p, входящая в t дважды и не пересекаясь
{{Задача
|definition=
Поиск самой длинной строки <tex>p</tex>, входящей в строку <tex>t</tex> дважды и не пересекаясь за <tex>\mathrm{SA} + O(n).</tex>}}
==== Основные положения ====
# Переберем все пары <tex>i</tex> и <tex>j</tex> такие, что они удовлетворяют условиям 1 и 2 и возьмем среди них максимум по длине строки.
Этот алгоритм можно реализовать за <tex>O(n^3)</tex> или за <tex>O(n^2)</tex>. Однако, он не позволяет достигнуть нужной нам асимптотики.
==== Оптимальное решение ====
===== Идея =====
Таким образом, мы рассмотрим все строки, соответствующие условиям 1 и 2, и, следовательно, найдем ответ. Алгоритм корректный.
===== Оценка времени работы =====
Т.к. построение суффиксного массива и подсчет lcp выполняется за <tex>O(n)</tex> и для каждого суффикса мы выполняем <tex>O(1)</tex> операций, то итоговое время работы <tex>O(n)</tex>
==См. также==
