165
правок
Изменения
→Самая длинная строка p, входящая в t дважды и не пересекаясь
Введем два условия:
# <tex>\max(len_i|i|, len_j|j|) \geqslant \min(len_i|i|, len_j|j|) + |s|</tex>
# <tex>|s| = \min\limits_{i'\dots j'}(lcp_k)</tex>
Здесь и далее <tex>len_i</tex> означает длину суффикса <tex>i</tex>, а <tex>lcp_k</tex> обозначает значение <tex>lcp</tex> для суффикса <tex>k</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, обновляем ответ.
===== Оценка времени работы =====
Т.к. построение суффиксного массива и подсчет lcp выполняется за <tex>O(n)</tex> и для каждого суффикса мы выполняем <tex>O(1)</tex> операций, то итоговое время работы <tex>O(n)</tex>.
==См. также==
