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