Изменения
→Поиск лексикографически максимального суффикса строки
}}
Точно так же, как и структура, описанная в части о минимальном суффиксе, наша структура данных, не считая улучшенный суффиксный массив, содержит битовые вектора <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 и выбирать наибольшего из двух кандидатов в качестве ответа. Это демонстрирует следующая теорема:
|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> и компромисс между временем запросов и временем построения, описанные в пунктах 4.2 [[#Построение искомой структуры данных|здесь]] и 4.3[[#Компромисс|здесь]] соответственно, также легко адаптируются к нашей задаче. В случае поиска максимального суффикса, тем не менее, мы можем добиться времени построения <tex>\mathcal{O}(n)</tex>, как будет показано в пункте 5.2[[#Построение структуры данных|ниже]].
}}
<tex>\triangleleft</tex>
===Построение искомой структуры данных===
Наш алгоритм основывается на следующем понятии. Для <tex>1\leqslant p\leqslant j\leqslant 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> {{---}} максимальный суффикс самого себя.
'''''Пример (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> для выбора канонических подстрок, описанных в пункте 4.2[[#Построение искомой структуры данных|здесь]], которые образуют разбиение <tex>[</tex>1, <tex>j]</tex>. Два следующих результата описывают изменения списка <tex>j</tex>-активных позиций и диапазонов <tex>R_{j}^{\ell}</tex>, когда мы увеличиваем <tex>j</tex>.
{{Лемма
