Изменения

|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> |proof= We first show that <tex>T[\mu..j]</tex> is both a prefix and a suffix of <tex>T[m..j]</tex>. If <tex>T[m..j]=T[\mu..j]</tex> then we are done otherwise <tex>T[\mu..j]\prec T[m..j]</tex>. By the definition of the lexicographic order, either (1) <tex>T[\mu..j]</tex> is a prefix of <tex>T[m..j]</tex>, or (2) there exists <tex>\displaystyle \ell<\min(|T[\mu..j]|,\ |T[m..j]|)</tex> such that <tex>T[\mu..\mu+ \ell]=T[m..m+\ell]</tex>, and <tex>T[\mu+\ell+1]<T[m+\ell+1]</tex>. In Case (1) we have <tex> m<\mu</tex> and thus <tex>T[\mu..j]</tex> is a suffix of <tex>T[m..j]</tex> as well. Let us show that Case (2) is impossible. Indeed, it follows that <tex>T[\mu..]\prec T[m..]</tex>, but the lexicographically smallest suffix in <tex>Suf [i,\ j]</tex> is <tex>T[m..]</tex>. Hence <tex>T[\mu..j]$ is both a prefix and a suffix of <tex>T[m..j]$. If <tex>T[m..j]$ is border-free then <tex>\mu=m$. Otherwise <tex>T[\mu..j]$ is a border of <tex>T[m..j]$. Suppose <tex>T[\mu..j]$ is not the shortest non-empty border, then there exists a shorter border <tex>\beta$ of <tex>T[m..j]$. By definition <tex>\beta$ is a prefix of <tex>T[m..j]$ and thus is also a prefix of <tex>T[\mu..j]$. Therefore <tex>\beta\prec T[\mu..j]$, which is a contradiction.