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

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

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

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

Декомпозиция Линдона строки [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].

Лемма:

[math]s [/math], [math]t[/math] – простые и [math]s \lt t[/math] лексикографически. Тогда: 1. [math]s + t \lt t[/math] 2. [math]s + t[/math] — простая

Доказательство:

[math]\triangleright[/math]

1. Так как [math]s \lt t[/math], [math]\mathcal {9} i : s[i] \lt t[i][/math] и [math]s[j] = t[j][/math], [math]j \lt i \rightarrow s + t \lt t[/math] 2. [math]|s| \lt = |t|[/math] Пусть [math]u[/math] – суффикс строки [math]s + t[/math] 1) [math]|u| = |t| \rightarrow u = t \rightarrow u \gt s + t[/math] 2) [math]|u| \lt |t| -\gt u[/math] — суффикс [math]t[/math]. Так как [math]t[/math] – простая, [math]t \lt u \rightarrow s + t \lt t \lt u[/math] 3) [math]|u| \gt |t| \rightarrow s = s' + s''[/math], [math]u = s'' + t[/math]. Так как [math]s[/math] — простая, [math]s \lt s''[/math] и [math]|s''| \lt |s| -\gt s + t \lt s'' + t[/math]

[math]\triangleleft[/math]

Теорема:

Можно построить декомпозицию Линдона любой строки s, причем единственным образом.

Доказательство:

[math]\triangleright[/math]

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', если

[math]\triangleleft[/math]