Изменения
Новая страница: «{{Определение |id=def1. |definition='''Простая строка''' {{---}} строка, которая строго лексикографичес...»
{{Определение
|id=def1.
|definition='''Простая строка''' {{---}} строка, которая строго лексикографически меньше любого своего суффикса.
}}
{{Определение
|id=def2.
|definition='''Декомпозиция Линдона строки <tex>s</tex>''' {{---}} её разложение <tex>s = s_1 + s_2 + ... + s_k</tex>, где строки <tex>s_i</tex> просты, и при этом <tex>s_1 >= s_2 >= ... >= s_k</tex>.
}}
Лемма. s, t – простые и s < t лексикографически. Тогда:
1. s+t < t
2. s + t – простая
Доказательство:
1. Так как s < t существует i : s[i] < t[i] и s[j] = t[j], j < I → s + t < t
2. |s| <= |t|
Пусть u – суффикс строки s + t
1) |u| = |t| → u = t → u > s + t
2) |u| < |t| → u – суффикс t. Так как t – простая, t < u → s + t < t < u
3) |u| > |t| → s = s' + s'', u = s'' + t. Так как s – простая, s < s'' и |s''| < |s| → s + t < s'' + t
Теорема. Можно построить декомпозицию Линдона любой строки s, причем единственным образом.
Доказательство:
1. Существование.
Разобьем строку на символы. Будем их склеивать, если подряд идущие символы: s[i] < s[i+1]. Так как символ - простая строка, по лемме s[i..i+1] - тоже простая и s[i..i+1] < s[i].
Далее склеиваем строки, не удовлетворяющие условию s_1>=s_2>=. .. >= s_k.
Это конечный процесс, так как длина строки конечна → получим нужное разбиение.
Пусть существует хотя бы одно разбиение строки на простые слова.
Возьмем разбиение строки на простые слова (без условия s_1>=s_2>=. .. >= s_k) такое, чтобы k было минимально.
Пусть в нем есть s_i < s_(i+1), тогда эти строки можно сконкатернировать → получим разбиение с меньшим числом слов!!!
Получили: k – минимально ↔ нет s_i < s_(i+1)
2. Единственность.
Пусть существует несколько разбиений s=s_1 + s_2 + … + s_k = s_1' + s_2' + … + s_k',
удовлетворяющих условию теоремы.
Сравним длины первых двух слов s_1 и s_1', если |s_1| = |s_1'|, сравним вторые, и так далее.
Если у всех слов длины одинаковы, то разбиения совпадают!!!
Иначе существует s_i : |s_i| != |s_i'|
Покажем, что такого не может быть:
1) Пусть |s_i| > |s_i'|
Тогда s_i = s_i' + s_i+1' + … + t, где t – префикс s_j+1', i <= j
Получаем: s_i < t (так как s_i простая и по определению меньше своего суффикса),
t < s_j+1' (так как t – префикс),
s_j+1' < s_i' (по условию разбиения),
s_i' < s_i (их начало совпадает, и |s_i| < |s_i'| по предположению.
Получили: s_i < s_i !!!
2) Пусть |s_i| < |s_i'| - проверяется аналогично.
То есть не может быть строк s_i несовпадающей длины → разбиения равны.
|id=def1.
|definition='''Простая строка''' {{---}} строка, которая строго лексикографически меньше любого своего суффикса.
}}
{{Определение
|id=def2.
|definition='''Декомпозиция Линдона строки <tex>s</tex>''' {{---}} её разложение <tex>s = s_1 + s_2 + ... + s_k</tex>, где строки <tex>s_i</tex> просты, и при этом <tex>s_1 >= s_2 >= ... >= s_k</tex>.
}}
Лемма. s, t – простые и s < t лексикографически. Тогда:
1. s+t < t
2. s + t – простая
Доказательство:
1. Так как s < t существует i : s[i] < t[i] и s[j] = t[j], j < I → s + t < t
2. |s| <= |t|
Пусть u – суффикс строки s + t
1) |u| = |t| → u = t → u > s + t
2) |u| < |t| → u – суффикс t. Так как t – простая, t < u → s + t < t < u
3) |u| > |t| → s = s' + s'', u = s'' + t. Так как s – простая, s < s'' и |s''| < |s| → s + t < s'' + t
Теорема. Можно построить декомпозицию Линдона любой строки s, причем единственным образом.
Доказательство:
1. Существование.
Разобьем строку на символы. Будем их склеивать, если подряд идущие символы: s[i] < s[i+1]. Так как символ - простая строка, по лемме s[i..i+1] - тоже простая и s[i..i+1] < s[i].
Далее склеиваем строки, не удовлетворяющие условию s_1>=s_2>=. .. >= s_k.
Это конечный процесс, так как длина строки конечна → получим нужное разбиение.
Пусть существует хотя бы одно разбиение строки на простые слова.
Возьмем разбиение строки на простые слова (без условия s_1>=s_2>=. .. >= s_k) такое, чтобы k было минимально.
Пусть в нем есть s_i < s_(i+1), тогда эти строки можно сконкатернировать → получим разбиение с меньшим числом слов!!!
Получили: k – минимально ↔ нет s_i < s_(i+1)
2. Единственность.
Пусть существует несколько разбиений s=s_1 + s_2 + … + s_k = s_1' + s_2' + … + s_k',
удовлетворяющих условию теоремы.
Сравним длины первых двух слов s_1 и s_1', если |s_1| = |s_1'|, сравним вторые, и так далее.
Если у всех слов длины одинаковы, то разбиения совпадают!!!
Иначе существует s_i : |s_i| != |s_i'|
Покажем, что такого не может быть:
1) Пусть |s_i| > |s_i'|
Тогда s_i = s_i' + s_i+1' + … + t, где t – префикс s_j+1', i <= j
Получаем: s_i < t (так как s_i простая и по определению меньше своего суффикса),
t < s_j+1' (так как t – префикс),
s_j+1' < s_i' (по условию разбиения),
s_i' < s_i (их начало совпадает, и |s_i| < |s_i'| по предположению.
Получили: s_i < s_i !!!
2) Пусть |s_i| < |s_i'| - проверяется аналогично.
То есть не может быть строк s_i несовпадающей длины → разбиения равны.
