262
правки
Изменения
→Поиск лексикографически минимального суффикса строки
Мы потребуем, чтобы канонические подстроки удовлетворяли определённым условиям:
*<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> соответственно
Такая структура данных работает при любом выборе канонических подстрок, которые удовлетворяют вышеприведённым условиям, например при простейшем <tex>|S^{l}_{j}| = \min(2^{l-1}, j)</tex>
==Ссылки==
