Изменения
Нет описания правки
|statement=<tex>s </tex>, <tex>t</tex> – простые и <tex>s < t</tex> лексикографически. Тогда:
1. <tex>s + t < t</tex>
2. <tex>s + t</tex> {{- --}} простая
|proof=
1. Так как <tex>s < t</tex>, существует <tex>\mathcal {9} i : s[i] < t[i]</tex> и <tex>s[j] = t[j]</tex>, <tex>j < i</tex> -> <tex>\rightarrow s + t < t</tex>
2. <tex>|s| <= |t|</tex>
Пусть <tex>u</tex> – суффикс строки <tex>s + t</tex>
1) <tex>|u| = |t| -> \rightarrow u = t -> \rightarrow u > s + t</tex>
2) <tex>|u| < |t| -> u</tex> {{---}} суффикс <tex>t</tex>. Так как <tex>t</tex> – простая, <tex>t < u -> \rightarrow s + t < t < u</tex>
3) <tex>|u| > |t| -> \rightarrow s = s' + s''</tex>, <tex>u = s'' + t</tex>. Так как <tex>s</tex> {{---}} простая, <tex>s < s''</tex> и <tex>|s''| < |s| -> s + t < s'' + t</tex>
}}
1. Существование.
Разобьем строку на символы. Будем их склеивать, если подряд идущие символы: s[i] < s[i+1]. Так как символ - простая строка, по лемме s[i..i+1] - тоже простая и s[i..i+1] < s[i].
Далее склеиваем строки, не удовлетворяющие условию s_1>=s_2>=. .. >= s_k.
Это конечный процесс, так как длина строки конечна → получим нужное разбиение.
Получили: s_i < s_i !!!
2) Пусть |s_i| < |s_i'| - проверяется аналогично.
То есть не может быть строк s_i несовпадающей длины → \rightarrow разбиения равны.
}}
