Изменения
→Поиск лексикографически максимального суффикса строки
<tex>(a) T[p..j]</tex>, либо
<tex>(b)</tex> максимальному суффиксу строки <tex>S_{j}^{\alpha(i,j)}</tex>
|proof=
Доказательство приводится ниже, с использованием вспомогательных лемм.
}}
Точно так же, как и структура, описанная в части о минимальном суффиксе, наша структура данных, не считая улучшенный суффиксный массив, содержит битовые вектора <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>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>-активна)
'''''Пример(12):''''' Если <tex>T[1..8]=dcccabab</tex>, то 8-активными позициями будут <tex>1, \ 2, \ 3, \ 4, \ 6, \ 8.</tex>
Алгоритм построения перебирает <tex>j</tex> от 1 до <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>.
}}
'''''Пример(14):''''' Если <tex>T[1..9]=dcccababb</tex>, то 8-активными позициями будут: <tex>1, \ 2, \ 3, \ 4, \ 6, \ 8, </tex> и 9-активными позициями будут: <tex>1, \ 2, \ 3, \ 4, \ 8, \ 9, </tex> т.е. мы добавляем <tex>9 </tex> в наш список 8-активных позиций, а затем удаляем <tex>6</tex>.
{{Теорема
