Изменения
→Поиск лексикографически минимального суффикса строки
Покажем, что <tex>\forall\tau: 1\le\tau\le\log{n}</tex> существует структура данных, размер которой линейно зависит от длины данного текста, со временем запроса <tex>O(\tau)</tex> и временем препроцессинга <tex>O(n\log{n/\tau})</tex> для запросов на нахождение минимального суффикса.
Будем обозначать <tex>SA(T)</tex> и <tex>ISA(T)</tex> суффиксный массив и инвертированный суффиксный массив строки <tex>T</tex> соответственно. Для данных индексов <tex>i<j</tex> будем обозначать <tex>Suf[i,j]</tex> массив <tex>\{T[i,i+1, \ldots ,|T|-1], \ldots , T[j,j+1, \ldots ,|T|-1]\}</tex>. SA и ISA могут быть улучшены за <tex>O(n)</tex>, чтобы отвечать на запросы вида
* по данным подстрокам <tex>x</tex> и <tex>y</tex> строки <tex>T</tex> найти <tex>lcp(x,y)</tex> и определить, какая из подстрок лексикографически меньше
* по индексам <tex>i</tex> и <tex>j</tex> вычислить максимальный и минимальный суффикс в <tex>Suf[i,j]</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>.
Мы потребуем, чтобы канонические подстроки удовлетворяли определённым условиям:
==Ссылки==
