3622
правки
Изменения
→Существование и единственность: рефакторинг доказательства
|statement=<tex>s </tex>, <tex>t</tex> {{---}} простые и <tex>s < t</tex> лексикографически. Тогда верны следующие утверждения:
<tex> 1. </tex> <tex>s + t < t</tex>
<tex> 2. </tex> <tex>s + t</tex> {{---}} простая
|proof=
<tex>1. </tex> Так как <tex>s < t</tex>, то <tex>\exists i : s[i] < t[i]</tex> и <tex>s[j] = t[j]</tex>, <tex>j < i \Rightarrow s + t < t</tex>
<tex>2. </tex> Пусть <tex>u</tex> {{---}} суффикс строки <tex>s + t</tex>. Тогда рассмотрим <tex> 3 </tex> возможных случая:
* <tex>|u| = |t| \Rightarrow u = t \Rightarrow u > s + t</tex> по пункту <tex> 1 </tex>.
* <tex>|u| < |t| \Rightarrow u</tex> {{---}} суффикс <tex>t</tex>. Так как <tex>t</tex> {{---}} простая, и <tex>t < u </tex> по определению <tex> \Rightarrow s + t < t < u</tex>
* <tex>|u| > |t| \Rightarrow s = s' + s''</tex>, <tex>u = s'' + t</tex>. Так как <tex>s</tex> {{---}} простая, то её суффикс <tex> s'' </tex> меньше самой строки <tex> s </tex> в каком символе, значит, <tex> s + t < s'' + t</tex>
|statement=Можно построить декомпозицию Линдона любой строки <tex>s</tex>, причем единственным образом.
|proof=
'''1. Существование.'''
У каждой строки существует хотя бы одно разбиение на простые слова. Это следует из того, что отдельный символ является простым словом. Тогда среди всех разбиений строки на простые слова возьмём то, в котором меньше всего слов. Покажем, что это и будет декомпозицией Линдона данной строки.
Таким образом доказали даже более сильное утверждение: <tex>s = s_1 s_2 ... s_k</tex>, <tex> k </tex> {{---}} минимально <tex>\Leftrightarrow</tex> нет <tex>s_i < s_{i+1}</tex>
'''2. Единственность.'''
Пусть существует несколько разбиений <tex>s = s_1s_2...s_k = s_1's_2'...s_k'</tex>,
Покажем, что такого не может быть:
<tex> 1) </tex> Пусть <tex>|s_i| > |s_i'|</tex>, тогда <tex>s_i = s_i's_{i+1}'...t</tex>, где <tex>t</tex> {{---}} префикс <tex>s_{j+1}'</tex>, <tex>i < j</tex>. Тогда получаем:* <tex>s_i < t</tex> (<tex>s_i</tex> {{---}} простая cтрока и по определению меньше своего суффикса)* <tex>t < s_{j+1}'</tex> (<tex>t</tex> {{---}} префикс <tex>s_{j+1}'</tex>)* <tex>s_{j+1}' \leqslant s_i'</tex> (по условию разбиения)* <tex>s_i' < s_i</tex> (их начало совпадает, и <tex>|s_i| < |s_i'|</tex> по предположению)Пришли к противоречию: <tex>s_i < s_i</tex>.
То есть не может быть строк <tex>s_i</tex> несовпадающей длины, значит, разбиения равны.
