262
правки
Изменения
→Поиск лексикографически минимального суффикса строки
Покажем, что <tex>\forall\tau: 1\leqslant\tau\log{n}</tex> существует структура данных, размер которой линейно зависит от длины данного текста, со временем запроса <tex>O(\tau)</tex> и временем препроцессинга <tex>O(n\log{n/\tau})</tex> для запросов на нахождение минимального суффикса.
Для данных индексов <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 Суффиксный массив и наибольший общий префикс двух строк]</ref> и определить, какая из подстрок лексикографически меньше
* по индексам <tex>i</tex> и <tex>j</tex> вычислить максимальный и минимальный суффикс в <tex>Suf[i,j]</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> мы выберем <tex>O(logN\log{N})</tex> подстрок <tex>T[k..j]</tex>, которые мы назовём каноническими. Определим как <tex>S^{l}_{j}</tex> <tex>l</tex>-ю кратчайшую каноническую подстроку, заканчивающуюся в позиции <tex>j</tex>. Для пары целых чисел <tex>1\leqslant i<j\leqslant n</tex> мы определим как <tex>\alpha(i,j)</tex> наибольшее <tex>l</tex>, такое, что <tex>S^{l}_{j}</tex> {{---}} суффикс <tex>T[i..j]</tex>.
Мы потребуем, чтобы канонические подстроки удовлетворяли определённым условиям:
*<tex>S^{1}_{j} = T[j..j]</tex> и для некоторого <tex>l=O(logN\log{N})</tex> выполняется <tex>S^{l}_{j} = T[1..j]</tex>
*<tex>\forall l:|S^{l+1}_{j}|\leqslant 2|S^{l}_{j}|</tex>
*<tex>\alpha(i,j)</tex> и <tex>|S^{l}_{j}|</tex> можно вычислить за константное время для данных <tex>(i,j)</tex> и <tex>(i,l)</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 в <ref name="ref2">[http://ge.tt/api/1/files/5uKJjWQ/0/blob?download Factorizing words over an ordered alphabet]</ref>). Разделим <tex>T</tex> на куски длиной <tex>2^{m}</tex>(где <tex>m=\lfloor\ell/2\rfloor-1</tex>) и запустим этот алгоритм для каждых четырёх (или менее, в конце) последовательных кусков. Это даст нам минимальные суффиксы <tex>S_{j}^{\ell}</tex> для всех <tex>1\leqslant j\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'\leqslant\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'\leqslant k</tex>, такой, что <tex>B[k']=1</tex>, и нам будет известно, что <tex>\ell'\in(\tau(k'-1),\ \tau k']</tex>. В общем случае, мы выберем наибольший <tex>k</tex>, такой что <tex>\tau k\leqslant\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>.
'''Из вышеописанного следует теорема:'''
{{Теорема
|author=5
|statement=
Для любого <tex>1\leqslant\tau\leqslant\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>.
}}
