8
правок
Изменения
Нет описания правки
|author=7
|id=lemma
|statement= Рассмотрим подстроку <tex>T[i..j]</tex>. Используя улучшенный суффиксный массив строки <tex>T</tex>, за <tex>\mathcal{O}(1)</tex> времени можно найти такой индекс <tex>p(i\leq p\leq j)</tex> такой, что максимальный суффикс <tex>T[\mu..j]</tex> строки <tex>T[i..j]</tex> равен либо
<tex>(a) T[p..j]</tex>, либо
<tex>(b)</tex> максимальный суффикс максимальному суффиксу строки <tex>S_{j}^{\alpha(i,j)}</tex>
|proof= Точно так же, как и структура, описанная в части о минимальном суффиксе, наша структура данных, не считая улучшенный
}}
===Доказательство основной леммы 7===
Ниже мы описываем алгоритм, работающий за константное время, который возвращает позицию <tex>p\in[i,\ j]</tex>.
<tex>\triangleleft</tex>
===Построениеискомой структуры данных===
Наш алгоритм основывается на следующем понятии. Для <tex>1\leq p\leq j\leq n</tex> мы говорим, что позиция <tex>p</tex> <tex>j</tex>-активна, если не существует такой позиции <tex>p'\in\{p+1,\ \ldots,\ j\}</tex>, что <tex>T[p'..j]\succ T[p..j]</tex>. Другими словами, <tex>p</tex> — <tex>j</tex>-активна тогда и только тогда, когда <tex>T[p..j]</tex> — максимальный суффикс самого себя.
'''''Пример:''''' Если <tex>T[1..9]=dcccababb</tex>, то 8-активными позициями будут: 1, 2, 3, 4, 6, 8, и 9-активными позициями будут: 1, 2, 3, 4, 8, 9, т.е. мы добавляем 9 в наш список 8-активных позиций, а затем удаляем 6.
{{Теорема
|id=theorem
|author=15
|statement=
Пусть <tex>j\in[1,\ n]</tex> и предположим, что <tex>2^{k}</tex> — максимальная степень двойки, которой кратно <tex>j</tex>.
<tex>(a)</tex> Если <tex>\ell=1</tex>, то <tex>R_{j}^{\ell}=[j,\ j]</tex>.
<tex>(b)</tex> Если <tex>2\leq\ell<2k+4</tex>, то <tex>R_{j}^{\ell}=R_{j-1}^{\ell-1}</tex>.
<tex>(c)</tex> Если <tex>\ell=2k+4</tex>, то <tex>R_{j}^{\ell}=R_{j-1}^{\ell}\cup R_{j-1}^{\ell-1}</tex>.
<tex>(d)</tex> Если <tex>\ell>2k+4</tex>, то <tex>R_{j}^{\ell}=R_{j-1}^{\ell}</tex>.
|proof= Заметим, что у нас есть <tex>R_{j}^{1}=[j,\ j]</tex> и <tex>R_{j}^{2}=[j-1,\ j-1]</tex>, в то время как для <tex>\ell>2</tex>
<tex>\ell>2 R_{j}^{\ell}=\left\{\begin{array}{ll}
[2^{m}(\lfloor\frac{j}{2^{m}}\rfloor-2)+1,2^{m-1}(\lfloor\frac{j}{2^{m-1}}\rfloor-3)] & \mathrm{i}\mathrm{f}\ \ell\ \mathrm{i}\mathrm{s}\ \mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n},\\
{[}2^{m}(\lfloor\frac{j}{2^{m}}\rfloor-3)+1,2^{m}(\lfloor\frac{j}{2^{m}}\rfloor-2)] & \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e},
\end{array}\right.</tex>
где <tex>m=\lfloor\ell/2\rfloor-1</tex>. Также заметим, что
<tex>2^{m}(\displaystyle \lfloor\frac{j}{2^{m}}\rfloor-3)=\left\{\begin{array}{l}
2^{m}(\lfloor\frac{j-1}{2^{m}}\rfloor-2)\ \mathrm{i}\mathrm{f}\ 2^{m}|j\\
2^{m}(\lfloor\frac{j-1}{2^{m}}\rfloor-3)\ \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e},
\end{array}\right.</tex>
<tex>2^{m}(\displaystyle \lfloor\frac{j}{2^{m}}\rfloor-2)=\left\{\begin{array}{ll}
2^{m-1}(\lfloor\frac{j-1}{2^{m-1}}\rfloor-3) & \mathrm{i}\mathrm{f}\ 2^{m}|j\\
2^{m}(\lfloor\frac{j-1}{2^{m}}\rfloor-2) & \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}.
\end{array}\right.</tex>
Более того, <tex>2^{m}|j\Leftrightarrow\ell\leq 2k+3</tex> и <tex>2^{m-1}|j\Leftrightarrow\ell\leq 2k+5</tex>, что упрощает проверку заявленных формул. Заметим, что возможно, что <tex>R_{j}^{\ell}</tex> определено только для значений <tex>\ell</tex>, меньших, чем <tex>2k+4</tex>. Это именно тот случай, когда число диапазонов растёт на единицу, иначе оно остается неизменным.
}}
[[Файл:image002.png|Рис. 2|800px]]
'''Рис. 2''' Разбиения <tex>[</tex>1, <tex>j]</tex> на <tex>R_{j}^{\ell}</tex> при <tex>j=27</tex> и <tex>j=28</tex>. При <tex>j=28</tex>, <tex>k=2</tex> и <tex>2k+4=8,\ R_{27}^{7}</tex> и <tex>R_{27}^{8}</tex> объединяются в <tex>R_{28}^{8}</tex>. На самом деле, все длины <tex>|R_{j}^{\ell}|</tex> являются степенями двойки, но наш алгоритм не использует это наблюдение.
Мы просматриваем позиции строки <tex>T</tex> слева направо, вычисляя битовые вектора. Мы сохраняем список активных позиций и разбиение <tex>[</tex>1, <tex>j]</tex> на диапазоны <tex>R_{j}^{\ell}</tex>. Кроме того, для каждого диапазона мы храним счетчик, число внутренних активных позиций. Напомним, что <tex>B_{j}[\ell]=1</tex> только когда l-й счетчик не равен нулю. Чтобы эффективно обновить список <tex>(j-1)</tex>-активных позиций и получить список <tex>j</tex>-активных позиций, мы также храним для каждого <tex>j'</tex> список указателей на пары соседних позиций, таких, что одна из них должна быть удалена, когда мы достигнем <tex>j=j'</tex>. Всякий раз когда появляется новая пара соседних позиций <tex>p_{z},p_{z+1}</tex>, мы считаем <tex>L=</tex> lcp <tex>(T[p_{z}..],\ T[p_{z+1}..])</tex> и с этого момента наименьший <tex>j'=p_{z}+L</tex>, когда одна из них должна быть удалена из списка,
when one of them should be removed from the list, и вставляем указатель на пару <tex>p_{z},p_{z+1}</tex> в j'-й лист. Когда мы действительно достигнем <tex>j=j'</tex>, мы проследуем по указателю и проверим, что <tex>p_{\ell}</tex> и <tex>p_{\ell+1}</tex> по-прежнему являются соседями. Если это так, мы удаляем соответствующую позицию из списка активных позиций. Иначе мы ничего не делаем.
Из Леммы 13 следует, что два возможных обновления списка при переходе от <tex>j-1</tex> к <tex>j</tex> добавляют <tex>j</tex> или удаляют какую-то позицию из списка. Это гарантирует, что процесс удаления из Леммы 13 и процесс, который мы описали, эквивалентны.
Предположим, что мы уже знаем список <tex>(j-1)</tex>-активных позиций, битовый вектор <tex>B_{j-1}</tex>, и число <tex>(j-1)</tex>-активных позиций в каждом диапазоне <tex>R_{j-1}^{\ell}</tex>. Сначала мы обновим список <tex>(j-1)</tex>-активных позиций. Когда позиция удалена из списка, мы находим диапазон, к которому она принадлежит и уменьшаем его счетчик внутренних позиций. Если счетчик становится нулевым, мы очищаем соответствующий бит битового вектора. Далее мы начинаем обновлять разбиение: сначала мы добавляем новый диапазон <tex>[j,\ j]</tex> к разбиению <tex>[1..j-1]</tex> и инициализируем счетчик активных позиций единицей. Затем, мы обновлям первые <tex>2k+4</tex> диапазонов (<tex>k</tex> — максимальная степень 2, которой кратно <tex>j</tex>), используя теорему 15, а также счетчики и битовый вектор. Этот процесс займет <tex>\mathcal{O}(k)</tex> времени, что амортизированно составляет <tex>\displaystyle \mathcal{O}(\sum_{k=1}^{\infty}\frac{k}{2^{k}})=\mathcal{O}(1)</tex> при всех значениях <tex>j</tex>.
{{Теорема
|id=theorem
|author=16
|statement= Строка <tex>T</tex> длины <tex>n</tex> может храниться в структуре данных памяти <tex>\mathcal{O}(n)</tex>, которая позволяет вычислять максимальный суффикс любой подстроки <tex>T</tex> за <tex>\mathcal{O}(1)</tex> времени. Данную структуру данных можно построить за <tex>\mathcal{O}(n)</tex> времени.
}}
==Ссылки==
