Изменения

|proof= По Лемме 1 из <ref name="ref1">[http://linkstarikovskaya.springerfiles.wordpress.com/chapter2013/10.100707/978on-3minimal-642and-38905maximal-4_5#pagesuffixes-1 of-a-substring.pdf On Minimal and Maximal Suffixes of a Substring]</ref> минимальный суффикс равен либо <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> {{---}} одна из базовых операций, поддерживаемых улучшенным суфмассивом.