Изменения
→Поиск лексикографически минимального суффикса строки
|id=lemma
|statement= Минимальный суффикс <tex>T[i..j]</tex> равен либо <tex>T[p..j]</tex>, где <tex>p</tex>-начальная позиция минимального суффикса в <tex>Suf[i,j]</tex>, либо минимальному суффиксу <tex>|S^{\alpha(i,j)}_{j}|</tex>. Более того, <tex>p</tex> может быть найдено за константное время с использованием
|proof= По лемме 1 из [http://link.springer.com/chapter/10.1007/978-3-642-38905-4_5#page-1 1] минимальный суффикс равен либо <tex>T[p..j]</tex>, либо его кратчайшему непустому бордеру. Более того, в последнем случае длина минимального суффикса равна не превышает <tex>\displaystyle \frac{1}{2}|T[p..j]|\leq\frac{1}{2}|T[i..j]|</tex>. С другой стороны, по второму свойству канониеских подстрок, длина <tex>S_{j}^{\alpha(i,j)}</tex> равна как минимум <tex>\displaystyle \frac{1}{2}|T[i..j]|</tex>. Таким образом, во втором случае минимальный суффикс <tex>T[i..j]</tex> является минимальным суффиксом <tex>S_{j}^{\alpha(i,j)}</tex>. Заметим, что для <tex>i=j</tex> значения <tex>\alpha(i,\ j)</tex> не определены, но тогда выполняется первый случай из условия леммы. Чтобы доказать финальное выражение, вспомним, что нахождение минимального суффикса <tex>Suf [i,\ j]</tex> - одна из базовых операций, поддерживаемых улучшенным суфмассивом.
}}
Требуемая структура данных, помимо улучшенного суфмассива, должна, для каждого <tex>j=1,\ \ldots,\ n</tex> содержать битовый вектор <tex>B_{j}</tex> длиной <tex>\alpha(1,\ j)</tex>. Положим <tex>B_{j}[\ell]=1</tex> тогда и только тогда, когда минимальный суффикс <tex>S_{j}^{\ell}</tex> длиннее, чем <tex>|S_{j}^{\ell-1}|</tex>. Для <tex>\ell=1</tex> мы всегда считаем <tex>B_{j}[1]=1</tex>, поскольку <tex>S_{j}^{1}</tex> является минимальным суффиксом самого себя. Вспомним, что количество канонических подстрок для каждого <tex>j</tex> равна <tex>\mathcal{O}(\log n)</tex> , поэтому каждый <tex>B_{j}</tex> вмещается в константное количество машинных слов и структура данных занимает <tex>\mathcal{O}(n)</tex> памяти.
===Запросы===
