Изменения

|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>.<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 либо <tex>(1) </tex> <tex>T[\mu..j]</tex> is a prefix of является префиксом <tex>T[m..j]</tex>, or либо <tex>(2) there exists </tex> существует <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 В случае <tex>(1) we have </tex> выполняется <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> является одновременно префиксом и суффиксом <tex>T[m..j]$</tex>. If Если <tex>T[m..j]$ is border-free then </tex> не имеет непустых бордеров, то <tex>\mu=m$</tex>. Otherwise Иначе, <tex>T[\mu..j]$ is a border of </tex> является бордером <tex>T[m..j]$</tex>. 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]$</tex>, тогда существует более короткий бордер <tex>\beta</tex>. By definition По определению, <tex>\beta$ is a prefix of </tex> {{---}} префикс <tex>T[m..j]$ and thus is also a prefix of </tex>, следовательно он также является префиксом <tex>T[\mu..j]$</tex>. Therefore Следовательно, <tex>\beta\prec T[\mu..j]$</tex>, which is a contradictionчто приводит нас к противоречию.

|id=lemmalemma2