Изменения
→Существование и единственность
{{Теорема
|id=theorem
|statement=Можно построить декомпозицию Линдона любой строки <tex>s</tex>, причем единственным образом.
|proof=
1. Существование.
Разобьем строку на символы. Будем их склеивать, если подряд идущие символы: <tex>s[i] < s[i+1]</tex>. Так как символ {{- --}} простая строка, по лемме <tex>s[i..i+1] </tex> {{- --}} тоже простая и <tex>s[i..i+1] < s[i]</tex>.Далее склеиваем строки, не удовлетворяющие условию <tex>s_1 >= s_2 >= ... >= s_k</tex>.Это конечный процесс, так как длина строки конечна → <tex>\rightarrow</tex> получим нужное разбиение.
Пусть существует хотя бы одно разбиение строки на простые слова.
Возьмем разбиение строки на простые слова (без условия <tex>s_1>=s_2>=. .. >= s_k</tex>) такое, чтобы <tex>k </tex> было минимально.Пусть в нем есть <tex>s_i < s_({i+1)}</tex>, тогда эти строки можно сконкатернировать → <tex>\rightarrow</tex> получим разбиение с меньшим числом слов!!!{{---}} противоречие с выбором <tex>k</tex>.
Получили: <tex>k – </tex> {{---}} минимально ↔ <tex>\leftrightarrow</tex> нет <tex>s_i < s_({i+1)}</tex>
2. Единственность.
Пусть существует несколько разбиений <tex>s=s_1 + s_2 + … ... + s_k = s_1' + s_2' + … ... + s_k'</tex>,
удовлетворяющих условию теоремы.
Сравним длины первых двух слов <tex>s_1 </tex> и <tex>s_1'</tex>, если <tex>|s_1| = |s_1'|</tex>, сравним вторые, и так далее.Если у всех слов длины одинаковы, то разбиения совпадают!!!{{---}} противоречие.Иначе существует <tex>\mathcal {9} s_i : |s_i| != \neq |s_i'|</tex>
Покажем, что такого не может быть:
1) Пусть <tex>|s_i| > |s_i'|</tex>Тогда <tex>s_i = s_i' + s_is_{i+1}' + … ... + t</tex>, где <tex>t – </tex> {{---}} префикс s_j<tex>s_{j+1}'</tex>, <tex>i <= j</tex> Получаем: <tex>s_i < t </tex> (так как <tex>s_i </tex> простая и по определению меньше своего суффикса), <tex>t < s_js_{j+1}' </tex> (так как <tex>t – </tex> {{---}} префикс), s_j<tex>s_{j+1}' < s_i' </tex> (по условию разбиения), <tex>s_i' < s_i </tex> (их начало совпадает, и <tex>|s_i| < |s_i'| </tex> по предположению. Получилипротиворечие: <tex>s_i < s_i !!!</tex>. 2) Пусть <tex>|s_i| < |s_i'| </tex> {{-- -}} проверяется аналогично. То есть не может быть строк <tex>s_i </tex> несовпадающей длины <tex>\rightarrow </tex> разбиения равны.
}}
==Алгоритм Дюваля==
