262
правки
Изменения
м
→Поиск лексикографически минимального суффикса строки
Запросы к перевёрнутому улучшенному суфмассиву <tex>T^{R}</tex>также имеют смысл. С его помощью мы можем для пары <tex>x,y</tex> подстрок <tex>T</tex> найти их наибольший общий суффикс <tex>lcs(x,y)</tex> и наибольшее число <tex>\alpha</tex>, такое, что <tex>x^{\alpha}</tex> является суффиксом <tex>y</tex>.
Возьмём строку <tex>T</tex> длины <tex>n</tex>. Для каждой позиции <tex>j</tex> мы выберем O(logN) подстрок <tex>T[k\ldots ..j]</tex>, которые мы назовём каноническими. Определим как <tex>S^{l}_{j}</tex> <tex>l</tex>-ю кратчайшую каноническую подстроку, заканчивающуюся в позиции <tex>j</tex>. Для пары целых чисел <tex>1\le i<j\le n</tex> мы определим как <tex>\alpha(i,j)</tex> наибольшее <tex>l</tex>, такое, что <tex>S^{l}_{j}</tex> - суффикс <tex>T[i \ldots ..j]</tex>.
Мы потребуем, чтобы канонические подстроки удовлетворяли определённым условиям:
*<tex>S^{1}_{j} = T[j \ldots ..j]</tex> и для некоторого <tex>l=O(logN)</tex> выполняется <tex>S^{l}_{j} = T[1 \ldots ..j]</tex>
*<tex>\forall l:|S^{l+1}_{j}|\le 2|S^{l}_{j}|</tex>
*<tex>\alpha(i,j)</tex> и <tex>|S^{l}_{j}|</tex> можно вычислить за константное время для данных <tex>(i,j)</tex> и <tex>(i,l)</tex> соответственно
{{Лемма
|id=lemma
|statement= Минимальный суффикс <tex>T[i\ldots ..j]</tex> равен либо <tex>T[p\ldots ..j]</tex>, где <tex>p</tex>-начальная позиция минимального суффикса в <tex>Suf[i,j]</tex>, либо минимальному суффиксу <tex>|S^{\alpha(i,j)}_{j}|</tex>. Более того, <tex>p</tex> может быть найдено за константное время с использованием
|proof=
}}
