Изменения
Нет описания правки
}}
{{Лемма. |id=lemma|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>i : s[i] < t[i] </tex> и <tex>s[j] = t[j]</tex>, <tex>j < I → i</tex> -> <tex>s + t < t</tex>2. <tex>|s| <= |t|</tex>Пусть u – суффикс строки s + t1) |u| = |t| → u = t → u <tex> s + t2) |u| < |t| → u /tex> – суффикс t. Так как t – простая, t строки < u → tex>s + t < t < u3) |u| /tex> |t| → s = s' + s'', u = s'' + t. Так как s – простая, s < s'' и |s''| < |s| → s + t < s'' + t
1) <tex>|u| = |t| -> u = t -> u > s + t</tex> 2) <tex>|u| < |t| -> u</tex> {{---}} суффикс <tex>t</tex>. Так как <tex>t</tex> – простая, <tex>t < u -> s + t < t < u</tex> 3) <tex>|u| > |t| -> s = s' + s''</tex>, <tex>u = s'' + t</tex>. Так как <tex>s</tex> {{---}} простая, <tex>s < s''</tex> и <tex>|s''| < |s| -> s + t < s'' + t</tex>}} {{Теорема. |id=theorem|statement=Можно построить декомпозицию Линдона любой строки s, причем единственным образом. Доказательство:|proof=
1. Существование.
Разобьем строку на символы. Будем их склеивать, если подряд идущие символы: s[i] < s[i+1]. Так как символ - простая строка, по лемме s[i..i+1] - тоже простая и s[i..i+1] < s[i].
2. Единственность.
Сравним длины первых двух слов s_1 и s_1', если |s_1| = |s_1'|, сравним вторые, и так далее.
Если у всех слов длины одинаковы, то разбиения совпадают!!!
2) Пусть |s_i| < |s_i'| - проверяется аналогично.
То есть не может быть строк s_i несовпадающей длины → разбиения равны.
}}
