Изменения
→Поиск лексикографически минимального суффикса строки
|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 из [1] минимальный суффикс равен либо <tex>T[p..j]</tex>, либо его кратчайшему непустому бордеру. Более того, в последнем случае длина минимального суффикса равна как максимум <tex>\displaystyle \frac{1}{2}|T[p..j]|\leq\frac{1}{2}|T[i..j]|</tex>. On the other hand, from the property (b) of canonical substrings we have that the length of <tex>S_{j}^{\alpha(i,j)}</tex> is at least <tex>\displaystyle \frac{1}{2}|T[i..j]|</tex>. Thus, in the second case the minimal suffix of <tex>T[i..j]</tex> is the minimal suffix of <tex>S_{j}^{\alpha(i,j)}</tex>. Note that for <tex>i=j</tex> the values <tex>\alpha(i,\ j)</tex> are not well-defined, but then case (a) holds. To prove the final statement, recall that finding the minimal suffix in <tex>Suf [i,\ j]</tex> is one of the basic queries supported by the enhanced suffix array.
}}
===Запросы===
==Ссылки==
