Изменения
→Построение искомой структуры данных
===Построение искомой структуры данных===
Простой алгоритм построения с временем работы <tex>\mathcal{O}(n\log n)</tex> также основывается на Лемме 1. Покажем, что построив улучшенный суфмассив, мы можем найти <tex>B_{j}</tex> за <tex>\mathcal{O}(\log n)</tex>. Мы ищем минимальный суффикс <tex>S_{j}^{\ell}</tex> для последовательных значений <tex>\ell</tex>. Как только мы получили результат <tex>\ell-1</tex>, первый случай Леммы 1 даёт нам второго кандидата на минимальный суффикс <tex>S_{j}^{\ell}</tex>, и наш улучшенный суфмассив позволяет нам выбрать наименьшего из этих двух кандидатов. Мы устанавливаем <tex>B_{j}[\ell]=1</tex> если меньший кандидат не содержится в <tex>S_{j}^{\ell-1}</tex>. Стало быть, мы получили следующий результат:
{{Теорема
|author=2
|statement=
Строку <tex>T</tex> длины <tex>n</tex> можно уместить в структуру данных с <tex>\mathcal{O}(n)</tex> памяти, которая позволяет вычислять минимальный суффикс любой подстроки <tex>T</tex> за <tex>\mathcal{O}(1)</tex>. Эта структура данных может быть построена за <tex>\mathcal{O}(n\log n)</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 2|S_{j}^{\ell-1}|</tex>, и, посему, нам необходимо немного изменить его.
Для <tex>\ell=1</tex> мы определим <tex>S_{j}^{1}=T[j..j]</tex>. Для <tex>\ell>1</tex> установим <tex>m=\lfloor\ell/2\rfloor-1</tex> и определим <tex>S_{j}^{\ell}</tex> таким образом:
<tex>
|S_{j}^{\ell}|=
\begin{cases}
2 \cdot 2^{m}+(j\ mod\ 2^{m}),& \ell \ mod \ 2 = 0\\
3 \cdot 2^{m}+(j\ mod\ 2^{m}),& \textup{otherwise}
\end{cases}</tex>
Заметим, что если <tex>2 \cdot 2^{m}\leq j<3\cdot 2^{m}</tex>, то <tex>T[1..j]=S_{j}^{2m+2}</tex>, в то время как, если <tex>3 \cdot 2^{m}\leq j<4\cdot 2^{m}</tex>, то <tex>T[1..j]=S_{j}^{2m+3}</tex>. Очевидно, что количество таких подстрок, заканчивающихся в <tex>j</tex> получается <tex>\mathcal{O}(\log n)</tex>. Докажем далее, что канонические подстроки, выбранные вышеуказанным способом, имеют необходимые свойства.
{{Теорема
|author=3
|statement=
Для любого <tex>S_{j}^{\ell}</tex> и <tex>S_{j}^{\ell+1}</tex> при <tex>\ell\geq 1</tex> мы имеем <tex>|S_{j}^{\ell+1}|<2|S_{j}^{\ell}|</tex>
|proof= Для <tex>\ell=1</tex> неравенство, очевидно, выполняется. Рассмотрим <tex>\ell\geq 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 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 2\cdot(3\cdot 2^{m}+(j\ mod \ 2^{m}))=2|S_{j}^{\ell}|</tex>
}}
{{Теорема
|author=4
|statement= Для <tex>1\leq i<j\leq n</tex>, величина <tex>\alpha(i,\ j)</tex> может быть посчитана за константное время.
|proof= Положим <tex> m=\lfloor\log|T[i..j]|\rfloor</tex>. Заметим, что
<tex>|S_{j}^{2m-1}|=3\cdot 2^{m-2}+(j \ mod \ 2^{m-2})<2^{m}\leq|T[i..j]|</tex>
<tex>|S_{j}^{2m+2}|=2\cdot 2^{m}+(j \ mod \ 2^{m})\geq 2^{m+1}>|T[i..j]|</tex>.
Таким образом, <tex>\alpha(i,\ j)\in\{2m-1,2m,\ 2m+1\}</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 [5]). Разделим <tex>T</tex> на куски длиной <tex>2^{m}</tex>(где <tex>m=\lfloor\ell/2\rfloor-1</tex>) и запустим этот алгоритм для каждых четырёх (или менее, в конце) последовательных кусков. Это даст нам минимальные суффиксы <tex>S_{j}^{\ell}</tex> для всех <tex>1\leq j\leq 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> требуемой памяти.
==Ссылки==
