Декомпозиция Линдона

Определение:

Простая строка — строка, которая строго лексикографически меньше любого своего суффикса.

Определение:

Декомпозиция Линдона строки [math]s[/math] — её разложение [math]s = s_1 + s_2 + ... + s_k[/math], где строки [math]s_i[/math] просты, и при этом [math]s_1 \gt = s_2 \gt = ... \gt = s_k[/math].

Лемма. 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 несовпадающей длины → разбиения равны.