262
правки
Изменения
м
→Поиск лексикографически минимального суффикса строки
Такая структура данных работает при любом выборе канонических подстрок, которые удовлетворяют вышеприведённым условиям, например при простейшем <tex>|S^{l}_{j}| = \min(2^{l-1}, j)</tex>
{{Лемма
|id=lemma
|author=0
|statement= Пусть <tex>T[\mu..j]</tex> - искомый лексикографически наименьший суффикс. Если у <tex>T[m..j]</tex> нет непустых бордеров, то <tex>T[\mu..j] = T[m..j]</tex>. Otherwise <tex>T[\mu..j]</tex> {{---}} кратчайший непустой бордер <tex>T[m..j]</tex>.
|proof= Приведено в <ref name="ref1">[http://starikovskaya.files.wordpress.com/2013/07/on-minimal-and-maximal-suffixes-of-a-substring.pdf On Minimal and Maximal Suffixes of a Substring]</ref>
}}
{{Лемма
|id=lemma
Более того, <tex>p</tex> может быть найдено за константное время с использованием улучшенного суффиксного массива строки <tex>T</tex>.
|proof= По Лемме 1 из <ref name="ref1">[http://starikovskaya.files.wordpress.com/2013/07/on-minimal-and-maximal-suffixes-of-a-substring.pdf On Minimal and Maximal Suffixes of a Substring]</ref> 0 минимальный суффикс равен либо <tex>T[p..j]</tex>, либо его кратчайшему непустому бордеру. Более того, в последнем случае длина минимального суффикса равна не превышает <tex>\displaystyle \frac{1}{2}|T[p..j]|\leqslant\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>(a)</tex> из условия леммы. Чтобы доказать финальное выражение, вспомним, что нахождение минимального суффикса <tex>Suf [i,\ j]</tex> {{---}} одна из базовых операций, поддерживаемых улучшенным суфмассивом.
}}
