262
правки
Изменения
м
→Поиск лексикографически минимального суффикса строки
Для данных индексов <tex>i<j</tex> будем обозначать как <tex>Suf[i,j]</tex> массив <tex>\{T[i\ldots], \ldots , T[j\ldots]\}</tex> - подмассив с индекса <tex>i</tex> по <tex>j</tex> массива всех суффиксов строки. Множество всех непустых суффиксов строки <tex>Suf[1,|T|]</tex> будем обозначать для краткости как <tex>Suf</tex>. Также, будем обозначать <tex>SA(T)</tex> и <tex>ISA(T)</tex> [[суффиксный массив ]] и инвертированный суффиксный массив строки <tex>T</tex> соответственно. <tex>SA</tex> и <tex>ISA</tex> могут быть улучшены за <tex>O(n)</tex>, чтобы отвечать на запросы вида
* по данным подстрокам <tex>x</tex> и <tex>y</tex> строки <tex>T</tex> найти [http://en.wikipedia.org/wiki/LCP_array наибольший общий префикс] <tex>lcp(x,y)</tex><ref name="ref3">[http://e-maxx.ru/algo/suffix_array Суффиксный массив и наибольший общий префикс двух строк]</texref> и определить, какая из подстрок лексикографически меньше
* по индексам <tex>i</tex> и <tex>j</tex> вычислить максимальный и минимальный суффикс в <tex>Suf[i,j]</tex>
