165
правок
Изменения
м
→Основные положения
==== Основные положения ====
Построим суффиксный массив строки <tex>t</tex> и посчитаем на нем [[Алгоритм_Касаи_и_др.|LCP]].
Рассмотрим какие-нибудь суффиксы <tex>i</tex> и <tex>j</tex> строки <tex>t</tex>. Обозначим их позиции в суффиксном массиве за <tex>i'</tex> и <tex>j'</tex>, причем <tex>i' \leq leqslant j'</tex>.
Будем говорить, что строка <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> соответствуют позициям этих вхождений.
Введем два условия:
# <tex>\max(len_i, len_j) \geq geqslant \min(len_i, len_j) + |s|</tex>
# <tex>|s| = \min\limits_{i'\dots j'}(lcp_k)</tex>
