3622
правки
Изменения
→Существование и единственность
|statement=<tex>s </tex>, <tex>t</tex> {{---}} простые и <tex>s < t</tex> лексикографически. Тогда верны следующие утверждения:
|proof=
* <tex>|u| = |t| \Rightarrow u = t \Rightarrow u > s + t</tex> по пункту <tex> 1 </tex>
* <tex>|u| < |t| \Rightarrow u</tex> {{---}} суффикс <tex>t</tex>. Так как <tex>t</tex> {{---}} простая, и <tex>t < u </tex> по определению <tex> \Rightarrow s + t < t < u</tex>
* <tex>|u| > |t| \Rightarrow s = s' + s''</tex>, <tex>u = s'' + t</tex>. Так как <tex>s</tex> {{---}} простая, то её суффикс <tex> s'' </tex> меньше самой строки <tex> s </tex> в каком символе, значит, <tex> s + t < s'' + t</tex>
Покажем, что такого не может быть:
* <tex>s_i < t</tex> (<tex>s_i</tex> {{---}} простая cтрока и по определению меньше своего суффикса)
* <tex>t < s_{j+1}'</tex> (<tex>t</tex> {{---}} префикс <tex>s_{j+1}'</tex>)
Пришли к противоречию: <tex>s_i < s_i</tex>.
То есть не может быть строк <tex>s_i</tex> несовпадающей длины, значит, разбиения равны.