==== Основные положения ====
Построим суффиксный массив строки <tex>t</tex> и посчитаем на нем [[Алгоритм_Касаи_и_др.|LCP]].
Рассмотрим какие-нибудь суффиксы <tex>i</tex> и <tex>j</tex> строки <tex>t</tex>. Обозначим их позиции в суффиксном массиве за <tex>i'</tex> и <tex>j'</tex>, причем <tex>i' \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> соответствуют позициям этих вхождений.
|author=
|statement=
Если для каких-нибудь суффиксов <tex>i</tex> и <tex>j</tex> соответствующая им Т.о. строка <tex>s</tex> удовлетворяет условиям 1 и 2, то она входит в <tex>t</tex> дважды и не пересекаясьтогда и только тогда, когда она удовлетворяет условию 1.
|proof=
Из того, что выполняется '''Необходимое условие 1 следует, что один из суффиксов хотя бы на <tex>|s|</tex> длиннее другого. При этом они оба начинаются со строки <tex>s</tex>. Поэтому строка <tex>s</tex> входит в <tex>t</tex> дважды и не пересекаясь.:'''
Условию 2 же Если строка удовлетворяет по построению<tex>s</tex> входит в <tex>t</tex> дважды и не пересекаясь, то один из суффиксов <tex>i</tex> и <tex>j</tex> хотя бы на <tex>|s|</tex> длиннее другого. Т.е. условие 1 выполнено.}}
{{Утверждение|author=|statement=Если строка <tex>s</tex> входит в <tex>t</tex> дважды и не пересекаясь, то соответствующие ей суффиксы <tex>i</tex> и <tex>j</tex> удовлетворяют условиям 1 и 2.|proof= Если строка <tex>s</tex> входит в <tex>t</tex> дважды и не пересекаясь, то один из суффиксов <tex>i</tex> и <tex>j</tex> хотя бы на <tex>|s|</tex> длиннее другого. Т.е. '''Достаточное условие 1 выполнено.:'''
Условие 2 Из того, что выполняетсяусловие 1 следует, т.к. иначе наибольший общий префикс что один из суффиксов хотя бы на <tex>i|s|</tex> и длиннее другого. При этом они оба начинаются со строки <tex>js</tex> был бы меньше . Поэтому строка <tex>|s|</tex>, чего не может быть по построению входит в <tex>st</tex>. Т.е. условие 2 тоже выполненодважды и не пересекаясь.
}}
Т.о. строка входит в <tex>t</tex> дважды и не пересекаясь тогда и только тогда, когда она удовлетворяет условиям 1 и 2.
==== Наивный алгоритм ====
