165
правок
Изменения
м
суфмас
==== Основные положения ====
Построим суфмас суффиксный массив строки <tex>t</tex> и посчитаем на нем LCP алгоритмом [[Алгоритм_Касаи_и_др.|Касаи, Аримуры, Арикавы, Ли, Парка]].Рассмотрим какие-нибудь суффиксы <tex>i</tex> и <tex>j</tex> строки <tex>t</tex>. Обозначим их позиции в суфмасе суффиксном массиве за <tex>i'</tex> и <tex>j'</tex>, причем <tex>i' \leq 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> соответствуют позициям этих вхождений.
