Изменения
Нет описания правки
==Основные определения==
{{Определение
|id=def1.
}}
==Существование и единственность==
{{Лемма
|id=lemma
|statement=<tex>s </tex>, <tex>t</tex> – {{---}} простые и <tex>s < t</tex> лексикографически. Тогда:
1. <tex>s + t < t</tex>
2. <tex>s + t</tex> {{---}} простая
1. Так как <tex>s < t</tex>, <tex>\mathcal {9} i : s[i] < t[i]</tex> и <tex>s[j] = t[j]</tex>, <tex>j < i \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>
То есть не может быть строк s_i несовпадающей длины \rightarrow разбиения равны.
}}
==Алгоритм Дюваля==
