Изменения

Перейти к: навигация, поиск

Суффиксный массив

11 байт добавлено, 19:25, 5 июня 2016
Основные положения
Будем говорить, что суффиксы <tex>i</tex> и <tex>j</tex> соответствуют строке <tex>s</tex>, если <tex>s</tex> входит в <tex>t</tex> дважды и не пересекаясь, а суффиксы <tex>i</tex> и <tex>j</tex> соответствуют позициям этих вхождений.
Для произвольной строки <tex>s </tex> и двух суффиксов, соответствующих ей, введем два условия:
# <tex>\max(|i|, |j|) \geqslant \min(|i|, |j|) + |s|</tex>
# <tex>|s| = \min\limits_{k=i'\dots j'}lcp[k]</tex>
165
правок

Навигация