Изменения

суффиксе, это Лемма лемма 1. Так как эта лемма неприменима к нашей задаче, далее мы докажем следующую лемму, эквивалентную в смысле

Точно так же, как и структура, описанная в части о минимальном суффиксе, наша структура данных, не считая улучшенный суффиксный массив, содержит битовые вектора <tex>B_{j},\ j\in[1,\ n]</tex>, с <tex>B_{j}[\ell]=1</tex>, если <tex>\ell=1</tex> или максимальный суффикс строки <tex>S_{j}^{\ell}</tex> длиннее <tex>|S_{j}^{\ell-1}|</tex>. Алгоритм запроса, описанный в части 4.1, очевидно, может быть адаптирован к нашей задаче, только вместо Леммы леммы 1 мы будем использовать Лемму лемму 7 и выбирать наибольшего из двух кандидатов в качестве ответа. Это демонстрирует следующая теорема:

Заметим, что если максимальный суффикс <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]

|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}|\geqslant|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], но здесь мы приводим доказательства вследствие другого обозначения.

[[Файл:image001.png|Рис. 1. Схематичная иллюстрация к Лемме лемме 11.|800px]]

'''Рис. 1:''' Схематичная иллюстрация к Лемме лемме 11.

'''Рис. 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>, когда одна из них должна быть удалена из списка, и вставляем указатель на пару <tex>p_{z},\ p_{z+1}</tex> в <tex>j'</tex>-й листсписок. Когда мы действительно достигнем <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> {{---}} максимальная степень <tex>2</tex>, которой кратно <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>.