Декомпозиция Линдона
| Определение: |
| Простая строка — строка, которая строго лексикографически меньше любого своего суффикса. |
| Определение: |
| Декомпозиция Линдона строки — её разложение , где строки просты, и при этом . |
Лемма. 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 несовпадающей длины → разбиения равны.
