Изменения
→Поиск лексикографически максимального суффикса строки
|statement= Строка <tex>T</tex> длины <tex>n</tex> может храниться в структуре данных с <tex>\mathcal{O}(n)</tex> памяти, которая позволяет вычислять максимальный суффикс любой подстроки строки <tex>T</tex> за время <tex>\mathcal{O}(1)</tex>.
|proof=
Алгоритмы построения за <tex>\mathcal{O}(n\log n)</tex> и компромисс между временем запросов и временем построения, описанные [[#Построение искомой структуры данных|здесь]] и [[#Компромисс|здесь]] соответственно, также легко адаптируются к нашей задаче. В случае поиска максимального суффикса, тем не менее, мы можем добиться времени построения <tex>\mathcal{O}(n)</tex>, как будет показано [[#Построение структуры данных|ниже]].
}}
'''''Пример (12):''''' Если <tex>T[1..8]=dcccabab</tex>, то 8-активными позициями будут <tex>1,\ 2,\ 3,\ 4,\ 6,\ 8.</tex>
Алгоритм построения перебирает <tex>j</tex> от <tex>1</tex> до <tex>n</tex>, сохраняя список активных позиций и вычисляя битовые вектора <tex>B_{j}</tex>. Мы также сохраняем диапазоны <tex>R_{j}^{\ell}</tex> для выбора канонических подстрок, описанных [[#Построение искомой структуры данных|здесь]], которые образуют разбиение <tex>[</tex>1, <tex>\ j]</tex>. Два следующих результата описывают изменения списка <tex>j</tex>-активных позиций и диапазонов <tex>R_{j}^{\ell}</tex>, когда мы увеличиваем <tex>j</tex>.
{{Лемма
Мы просматриваем позиции строки <tex>T</tex> слева направо, вычисляя битовые вектора. Мы сохраняем список активных позиций и разбиение <tex>[</tex>1, <tex>\ j]</tex> на диапазоны <tex>R_{j}^{\ell}</tex>. Кроме того, для каждого диапазона мы храним счетчик, число внутренних активных позиций. Напомним, что <tex>B_{j}[\ell]=1</tex> только когда <tex>l</tex>-й счетчик не равен нулю. Чтобы эффективно обновить список <tex>(j-1)</tex>-активных позиций и получить список <tex>j</tex>-активных позиций, мы также храним для каждого <tex>j'</tex> список указателей на пары соседних позиций, таких, что одна из них должна быть удалена, когда мы достигнем <tex>j=j'</tex>. Всякий раз когда появляется новая пара соседних позиций <tex>p_{z},\ p_{z+1}</tex>, мы считаем <tex>L=</tex> <tex>lcp</tex> <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 и процесс, который мы описали, эквивалентны.
