Изменения

Более того, такой <b>улучшенный суффиксный массив</b> может отвечать на запрос "по данным <tex>x,y</tex> - подстрокам <tex>T</tex> вычислить максимальное чило <tex>\alpha</tex>, такое, что <tex>x^{\alpha}</tex> является префиксом <tex>y</tex>" за константное время. Действительно, стоит заметить, что если <tex>x</tex> - префикс <tex>y = T[i..j]</tex>, то <tex>\alpha |x| \le lcp(T[i..j],T[i+|x|..j] < (\alpha+1)|x|)</tex>

Запросы к перевёрнутому улучшенному суфмассиву <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>.