Изменения

Поиск лексикографически минимального и максимального суффиксов строки {{- --}} вопрос, который часто поднимается при решении различных теоретических задач. С помощью классического алгоритма Дюваля эта задача решается за линейное время и константный размер дополнительной памяти.

Покажем, что <tex>\forall\tau: 1\leleqslant\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>. <tex>SA </tex> и <tex>ISA </tex> могут быть улучшены за <tex>O(n)</tex>, чтобы отвечать на запросы вида

Более того, такой <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 leqslant lcp(T[i..j],T[i+|x|..j] < (\alpha+1)|x|)</tex>

Возьмём строку <tex>T</tex> длины <tex>n</tex>. Для каждой позиции <tex>j</tex> мы выберем O(logN) подстрок <tex>T[k..j]</tex>, которые мы назовём каноническими. Определим как <tex>S^{l}_{j}</tex> <tex>l</tex>-ю кратчайшую каноническую подстроку, заканчивающуюся в позиции <tex>j</tex>. Для пары целых чисел <tex>1\le leqslant i<j\le leqslant n</tex> мы определим как <tex>\alpha(i,j)</tex> наибольшее <tex>l</tex>, такое, что <tex>S^{l}_{j}</tex> {{--- }} суффикс <tex>T[i..j]</tex>.

*<tex>\forall l:|S^{l+1}_{j}|\le leqslant 2|S^{l}_{j}|</tex>

<tex>(a)\ T[p..j]</tex>, где <tex>p</tex>{{---}} начальная позиция минимального суффикса в <tex>Suf[i,j]</tex>, либо

|proof= По Лемме 1 из [http://link.springer.com/chapter/10.1007/978-3-642-38905-4_5#page-1 5] минимальный суффикс равен либо <tex>T[p..j]</tex>, либо его кратчайшему непустому бордеру. Более того, в последнем случае длина минимального суффикса равна не превышает <tex>\displaystyle \frac{1}{2}|T[p..j]|\leqleqslant\frac{1}{2}|T[i..j]|</tex>. С другой стороны, по второму свойству канонических подстрок, длина <tex>S_{j}^{\alpha(i,j)}</tex> равна как минимум <tex>\displaystyle \frac{1}{2}|T[i..j]|</tex>. Таким образом, во втором случае минимальный суффикс <tex>T[i..j]</tex> является минимальным суффиксом <tex>S_{j}^{\alpha(i,j)}</tex>. Заметим, что для <tex>i=j</tex> значения <tex>\alpha(i,\ j)</tex> не определены, но тогда выполняется случай <tex>(a)</tex> из условия леммы. Чтобы доказать финальное выражение, вспомним, что нахождение минимального суффикса <tex>Suf [i,\ j]</tex> {{--- }} одна из базовых операций, поддерживаемых улучшенным суфмассивом.

Вышеописанная конструкция проста и работает для любого выбора канонических подстрок, но, к сожалению, она не может быть использована для достижения компромисса между временем запроса и временем построения. Далее мы предложим особый способ выбора канонических подстрок и опишем альтернативный метод построения. Этот способ основывается на предположении, что по данной строке длины <tex>k</tex> мы можем найти минимальный суффикс для всех её префиксов за <tex>\mathcal{O}(k)</tex>. Следовательно, нам удобно иметь много <tex>S_{j}^{\ell}</tex>, которые являются префиксами друг друга. Тогда, естественным будет выбрать <tex>|S_{j}^{\ell}|=2^{\ell-1}+(j\ mod\ 2^{\ell-1})</tex> , поскольку все подстроки <tex>S_{\alpha 2^{l-1}}^{\ell},\ S_{\alpha 2^{l-1}+1}^{\ell},\ \ldots,\ S_{(\alpha+1)2^{l-1}-1}^{\ell}</tex> являются префиксами <tex>S_{(\alpha+1)2^{l-1}-1}^{\ell}</tex>. К сожалению, подстроки, выбранные таким способом, не удовлетворяют условию <tex>|S_{j}^{\ell}|\leq leqslant 2|S_{j}^{\ell-1}|</tex>, и, посему, нам необходимо немного изменить его.

Заметим, что если <tex>2 \cdot 2^{m}\leq leqslant j<3\cdot 2^{m}</tex>, то <tex>T[1..j]=S_{j}^{2m+2}</tex>, в то время как, если <tex>3 \cdot 2^{m}\leq leqslant j<4\cdot 2^{m}</tex>, то <tex>T[1..j]=S_{j}^{2m+3}</tex>. Очевидно, что количество таких подстрок, заканчивающихся в <tex>j</tex> получается <tex>\mathcal{O}(\log n)</tex>. Докажем далее, что канонические подстроки, выбранные вышеуказанным способом, имеют необходимые свойства.

Для любого <tex>S_{j}^{\ell}</tex> и <tex>S_{j}^{\ell+1}</tex> при <tex>\ell\geq geqslant 1</tex> мы имеем <tex>|S_{j}^{\ell+1}|<2|S_{j}^{\ell}|</tex>|proof= Для <tex>\ell=1</tex> неравенство, очевидно, выполняется. Рассмотрим <tex>\ell\geq geqslant 2</tex>. Обозначим через <tex>m</tex>, как и ранее, <tex>\lfloor\ell/2\rfloor-1</tex>. Если <tex>\ell</tex> чётно, то <tex>\ell+1</tex> нечётно и мы имеем<tex>|S_{j}^{\ell+1}|=3\cdot 2^{m}+(j\ mod \ 2^{m})<4\cdot 2^{m}\leq leqslant 2\cdot(2\cdot 2^{m}+(j\ mod \ 2^{m}))=2|S_{j}^{\ell}|</tex>, в то время как, для нечётного <tex>\ell</tex> выполняется <tex>|S_{j}^{\ell+1}|=2\cdot 2^{m+1}+(j\ mod \ 2^{m+1})<3\cdot 2^{m+1}\leq leqslant 2\cdot(3\cdot 2^{m}+(j\ mod \ 2^{m}))=2|S_{j}^{\ell}|</tex>

|statement= Для <tex>1\leq leqslant i<j\leq leqslant n</tex>, величина <tex>\alpha(i,\ j)</tex> может быть посчитана за константное время.

<tex>|S_{j}^{2m-1}|=3\cdot 2^{m-2}+(j \ mod \ 2^{m-2})<2^{m}\leqleqslant|T[i..j]|</tex>

<tex>|S_{j}^{2m+2}|=2\cdot 2^{m}+(j \ mod \ 2^{m})\geq geqslant 2^{m+1}>|T[i..j]|</tex>.

После построения улучшенного суфмассива, мы установили все биты<tex>B_{j}[1]</tex> в 1. После этого, для каждого <tex>\ell>1</tex> мы посчитали минимальные суффиксы подстрок <tex>S_{j}^{\ell}</tex>, как указано далее. Зафиксируем <tex>\ell>1</tex> и разобьём <tex>T</tex> на куски размером <tex>2^{m}</tex>(где <tex>m=\lfloor\ell/2\rfloor-1</tex>) . Теперь каждый <tex>S_{j}^{\ell}</tex> является префиксом конкатенации максимум 4х таких кусков. Вспомним, что по данной строке можно посчитать длины минимальных суффиксов всех её префиксов за линейное время с помощью одной из вариаций алгоритма Дюваля (Алгоритм 3.1 in [http://www.sciencedirect.com/science/article/pii/0196677483900172 6]). Разделим <tex>T</tex> на куски длиной <tex>2^{m}</tex>(где <tex>m=\lfloor\ell/2\rfloor-1</tex>) и запустим этот алгоритм для каждых четырёх (или менее, в конце) последовательных кусков. Это даст нам минимальные суффиксы <tex>S_{j}^{\ell}</tex> для всех <tex>1\leq leqslant j\leq leqslant n</tex>, за время <tex>\mathcal{O}(n)</tex>. Значение <tex>B_{j}[\ell]</tex> определено с помощью сравнения длины вычисленного минимального суффикса <tex>S_{j}^{\ell}</tex> с <tex>|S_{j}^{\ell-1}|</tex>. У нас <tex>\mathcal{O}(\log n)</tex> фаз алгоритма, что даёт нам время <tex>\mathcal{O}(n\log n)</tex> и <tex>\mathcal{O}(n)</tex> требуемой памяти.

Как и ранее, предположим, что мы ищем минимальный суффикс <tex>T[i..j]</tex>, при <tex>\alpha(i,\ j)=\ell</tex>. Самое сложное в этом {{--- }} найти минимальный суффикс <tex>S_{j}^{\ell}</tex>, и далее необходимо найти <tex>\ell'\leqleqslant\ell</tex>, такой, что минимальный суффикс <tex>S_{j}^{\ell}</tex> на самом деле является минимальным суффиксом <tex>S_{j}^{\ell'}</tex>, но длиннее, чем <tex>|S_{j}^{\ell'-1}|</tex>. Если <tex>\ell=\tau k</tex> для целого <tex>k</tex>, мы можем найти наибольший <tex>k'\leq leqslant k</tex>, такой, что <tex>B[k']=1</tex>, и нам будет известно, что <tex>\ell'\in(\tau(k'-1),\ \tau k']</tex>. В общем случае, мы выберем наибольший <tex>k</tex>, такой что<tex>\tau k\leqleqslant\ell</tex>, и будем знать, что мы должны рассмотреть <tex>\ell'\in(\tau k,\ \ell]</tex> и <tex> \ell'\in(\tau(k'-1),\ \tau k']</tex>, где <tex>k'</tex> определён, как в предыдущем случае. В результате, мы имеем <tex>\mathcal{O}(\tau)</tex> возможных значений <tex>\ell'</tex>, и нам изестно, что искомый суффикс может быть найден, используя случай <tex>(a)</tex> Леммы 1 для <tex>S_{j}^{\ell'}</tex> для каждого из этих значений. Тогда мы просто сгенерируем всех этих кандидатов и используем улучшенный суфмассив, чтобы найти наименьший суффикс среди них. В результате, запрос к нашей структуре данных будет выполняться за <tex>\mathcal{O}(\tau)</tex>.

Для любого <tex>1\leqleqslant\tau\leqleqslant\log n</tex>, строка <tex>T</tex> длиной <tex>n</tex> может храниться в структуре данных, занимающей <tex>\mathcal{O}(n)</tex> памяти, позволяющей вычислять минимальный суффикс любой из подстрок <tex>T</tex> за время <tex>\mathcal{O}(\tau)</tex>. Такая структура данных может быть построена за <tex>\mathcal{O}(n\log n/\tau)</tex>.