Изменения
Нет описания правки
Ниже мы описываем алгоритм, работающий за константное время, который возвращает позицию <tex>p\in[i,\ j]</tex>.
Заметим, что если максимальный суффикс <tex>T[\mu..j]</tex> of <tex>T[i..j]</tex> короче, чем <tex>S_{j}^{\alpha(i,j)}</tex> (случай (b) Леммы 7), алгоритм может вернуть любое <tex>p\in[i,\ j]</tex>. Далее мы предполагаем, что <tex>T[\mu..j]</tex> длиннее, чем <tex>S_{j}^{\alpha(i,\ j)}</tex> и показываем, что при этом предположении алгоритм вернёт <tex> p=\mu</tex>. Из нашего предположения свойств канонических подстрок следует, что <tex>\mu\in[i,\ r]</tex>, where <tex>r=j-|S_{j}^{\alpha(i,\ j)}|</tex>, и что длины суффиксов подстроки <tex>T[i..j]</tex>, начинающихся с позиций в промежутке <tex>[i,\ r]</tex>, отличаются не более чем в два раза.
Мы начнем со вспомогательной леммы, которая обозначалась как Лемма 2 в [http://link.springer.com/chapter/10.1007/978-3-642-38905-4_5#page-1 6]
|id=lemma
|author=9
|statement= Пусть <tex>P_{1}=T[p_{1}..j]</tex> {{---}} префикс строки <tex>T[\mu..j]</tex> и пусть <tex>P_{2}=T[p_{2}..j]</tex>, где <tex>T[p_{2}..j]</tex> {{---}} максимальный суффикс в <tex>Suf [i,\ p_{1}-1]</tex>. Если <tex>P_{1}</tex> не является префиксом <tex>P_{2}</tex>, тогда <tex>\mu=p_{1}</tex>. Иначе, <tex>P_{2}</tex> также является префиксом строки <tex>T[\mu..j]</tex>.
|proof= Пусть <tex>T[p_{1}..]</tex> {{---}} максимальный суффикс в <tex>Suf [i,\ r]</tex> и <tex>T[p_{2}..]</tex> {{---}} максимальный суффикс в <tex>Suf [i,\ p_{1}-1]</tex>. Очевидно, <tex>P_{1}=T[p_{1}..j]</tex> является префиксом строки <tex>T[\mu..j]</tex>. Предположим, что <tex>P_{1}</tex> {{---}} префикс <tex>P_{2}</tex> (иначе <tex>p_{1}=\mu\</tex> по Лемме 9). Длины <tex>P_{1}</tex> и <tex>P_{2}</tex> различаются не более чем в два раза, поэтому <tex>2|P_{1}|\geq|P_{2}|</tex>. Благодаря этому, <tex>P_{1}</tex> и <tex>P_{2}</tex> имеют некоторые интересные свойства, описанные в последующих леммах. Эти леммы по существу повторяют Леммы 4 и 5 из [http://link.springer.com/chapter/10.1007/978-3-642-38905-4_5#page-1 6], но здесь мы приводим доказательства вследствие другого обозначения.
<tex>\triangleright</tex>
Пусть <tex>T[p_{1}..]</tex> {{---}} максимальный суффикс в <tex>Suf [i,\ r]</tex> и <tex>T[p_{2}..]</tex> {{---}} максимальный суффикс в <tex>Suf [i,\ p_{1}-1]</tex>. Сначала вычислим <tex>p_{1}</tex> и <tex>p_{2}</tex> за <tex>\mathcal{O}(1)</tex>, используя улучшенный суффиксный массив. Затем проверим, что <tex>T[p_{1}..j]</tex> является префиксом <tex>T[p_{2}..j]</tex>. Если это неверно, то мы возвращаем <tex>p=p_{1}</tex>. Иначе, мы вычисляем максимальное целое число <tex>r</tex>, такое, что <tex>\rho^{r}</tex> (для <tex>\rho=T[p_{2}..p_{1}-1])</tex>) {{---}} суффикс <tex>T[i..p_{1}-1]</tex>, используя метод из алгоритма поиска минимального суффикса, и возвращаем <tex>p=p_{1}-r|\rho|</tex>. Из вышеописанных лемм следует, что если <tex>T[\mu..j]</tex> длиннее <tex>S_{j}^{\alpha(i,\ j)}</tex>, тогда <tex> p=\mu</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[i..j]</tex> {{---}} это минимальная <tex>j</tex>-активная позиция в промежутке <tex>[i,\ j]</tex>. Следовательно, при <tex>\ell>1</tex> мы имеем <tex>B_{j}[\ell]=1</tex> тогда и только тогда, когда существует как минимум одна <tex>j</tex>-активная позиция в диапазоне <tex>R_{j}^{\ell}=[j-|S_{j}^{\ell}|+1, \ j-|S_{j}^{\ell-1}|]</tex>. Положим <tex>R_{j}^{1}=[j,\ j]</tex>, тогда это равенство также сохраняется для <tex>\ell=1</tex> (поскольку <tex>j</tex> всегда <tex>j</tex>-активна)
'''''Пример:''''' Если <tex>T[1..8]=dcccabab</tex>, то 8-активными позициями будут 1, 2, 3, 4, 6, 8.
<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>
'''Рис. 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 и процесс, который мы описали, эквивалентны.
