1632
правки
Изменения
м
rollbackEdits.php mass rollback
{{Определение
|id=def1.
|definition='''Простая строка''' {{---}} строка, которая лексикографически меньше любого своего собственного суффикса.
}}
2. <tex>s + t</tex> {{---}} простая
|proof=
1. Так как <tex>s < t</tex>, то либо <tex>s</tex> является префиксом <tex>t</tex>, тогда: <tex>s + t = s + s + x</tex> <tex>s + s + x < s + x</tex> <tex>s + x < x</tex> Следовательно <tex>t <</tex> любого суффикса <tex>t</tex> (так как по условию <tex>t</tex> явлеяется простой строкой), либо <tex>\exists i : s[i] < t[i]</tex> и <tex>s[j] = t[j]</tex>, <tex>j < i \Rightarrow </tex>. Из обоих ситуаций следует, что <tex> s + t < t</tex>
2. Пусть <tex>u</tex> {{---}} суффикс строки <tex>s + t</tex>. Тогда рассмотрим 3 возможных случая:
