Изменения
→Поиск лексикографически максимального суффикса строки
|proof= Поскольку <tex>P_{1}</tex> {{---}} бордер <tex>P_{2},\ \rho=T[p_{2}..p_{1}-1]</tex> {{---}} период <tex>P_{2}</tex>. Остается лишь доказать, что невозможно найти более короткий период. Таким образом, рассмотрим(consider) кратчайший период <tex>\gamma</tex>, и предположим, что <tex>|\gamma|<|\rho|</tex>. Тогда <tex>|\gamma|+|\rho|\leqslant 2|\rho|\leqslant|T[p_{2}..j]|</tex>, и по лемме о периодичности подстрока <tex>P_{2}</tex> имеет другой период <tex>\mathrm{g}\mathrm{c}\mathrm{d}(|\gamma|,\ |\rho|)</tex> . Так как <tex>\gamma</tex> {{---}} кратчайший период, то <tex>|\rho|</tex> должно быть степенью <tex>|\gamma|</tex>, т.е. <tex>\rho=\gamma^{k}</tex> для какого-то <tex>k\geqslant 2</tex>.
Предположим, что <tex>T[p_{1}..]\prec\gamma T[p_{1}..]</tex>'''(лексикографически меньше)'''. Тогда приписывание к обеим частям последнего неравенства степеней <tex>\gamma</tex> даёт <tex>\gamma^{\ell-1}T[p_{1}..]\prec\gamma^{\ell}T[p_{1}..]</tex> для любого <tex>1\leqslant\ell\leqslant k</tex>, таким образом из транзитивности <tex>\prec</tex> получаем <tex>T[p_{1}..]\prec\gamma^{k}T[p_{1}..]=T[p_{2}..]</tex>, что противоречит максимальности <tex>T[p_{1}..]</tex> in <tex>Suf[i,\ r]</tex>. Таким образом, <tex>T[p_{1}..]\succ\gamma T[p_{1}..]</tex>, и следовательно <tex>\gamma^{k-1}T[p_{1}..]\succ\gamma^{k}T[p_{1}..]</tex>. Но <tex>\gamma^{k-1}T[p_{1}..]=T[p_{2}+|\gamma|..]</tex> и <tex>\gamma^{k}T[p_{1}..]=T[p_{2}..]</tex>, поэтому <tex>T[p_{2}+|\gamma|..]</tex> больше, чем <tex>T[p_{2}..]</tex> и принадлежит <tex>Suf [i,\ p_{1}-1]</tex>, противоречие. Заметим, что на самом деле <tex>s\geqslant 2</tex>, потому что <tex>2|P_{1}|\geqslant|P_{2}|=|P_{1}|+|\rho|</tex>, поэтому <tex>|P_{1}|\geqslant|\rho|.\ </tex>
}}
