Декомпозиция Линдона — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Основные определения)
(Основные определения)
Строка 1: Строка 1:
 
==Основные определения==
 
==Основные определения==
 +
Декомпозиция Линдона была изобретена Роджером Линдоном (англ. ''Roger Lyndon'') в 1954 году. Она используется для нахождения лексикографически минимального и максимального суффиксов строки.
 +
 
{{Определение
 
{{Определение
 
|id=def1.  
 
|id=def1.  

Версия 21:39, 1 мая 2014

Основные определения

Декомпозиция Линдона была изобретена Роджером Линдоном (англ. Roger Lyndon) в 1954 году. Она используется для нахождения лексикографически минимального и максимального суффиксов строки.


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


Определение:
Декомпозиция Линдона (англ. Lyndon decomposition) строки [math]s[/math] — её разложение [math]s = s_1 + s_2 + ... + s_k[/math], где строки [math]s_i[/math] просты, и при этом [math]s_1 \geqslant s_2 \geqslant ... \geqslant 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| \leqslant |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| \rightarrow 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| \rightarrow s + t \lt s'' + t[/math]
[math]\triangleleft[/math]
Теорема:
Можно построить декомпозицию Линдона любой строки [math]s[/math], причем единственным образом.
Доказательство:
[math]\triangleright[/math]

1. Существование.

Разобьем строку на символы. Будем их склеивать, если подряд идущие символы: [math]s[i] \lt s[i+1][/math]. Так как символ — простая строка, по лемме [math]s[i..i+1][/math] — тоже простая и [math]s[i..i+1] \lt s[i][/math]. Далее склеиваем строки, не удовлетворяющие условию [math]s_1 \geqslant s_2 \geqslant ... \geqslant s_k[/math]. Это конечный процесс, так как длина строки конечна [math]\rightarrow[/math] получим нужное разбиение.

Пусть существует хотя бы одно разбиение строки на простые слова. Возьмем разбиение строки на простые слова (без условия [math]s_1 \geqslant s_2 \geqslant ... \geqslant s_k[/math]) такое, чтобы [math]k[/math] было минимально. Пусть в нем есть [math]s_i \lt s_{i+1}[/math], тогда эти строки можно сконкатернировать [math]\rightarrow[/math] получим разбиение с меньшим числом слов — противоречие с выбором [math]k[/math].

Получили: [math]k[/math] — минимально [math]\leftrightarrow[/math] нет [math]s_i \lt s_{i+1}[/math]

2. Единственность.

Пусть существует несколько разбиений [math]s = s_1 + s_2 + ... + s_k = s_1' + s_2' + ... + s_k'[/math], удовлетворяющих условию теоремы. Сравним длины первых двух слов [math]s_1[/math] и [math]s_1'[/math], если [math]|s_1| = |s_1'|[/math], сравним вторые и так далее. Если у всех слов длины одинаковы, то разбиения совпадают — противоречие. Иначе [math]\mathcal {9} s_i : |s_i| \neq |s_i'|[/math] Покажем, что такого не может быть:

1) Пусть [math]|s_i| \gt |s_i'|[/math] Тогда [math]s_i = s_i' + s_{i+1}' + ... + t[/math], где [math]t[/math] — префикс [math]s_{j+1}'[/math], [math]i \leqslant j[/math] Получаем: [math]s_i \lt t[/math] (так как [math]s_i[/math] простая и по определению меньше своего суффикса), [math]t \lt s_{j+1}'[/math] (так как [math]t[/math] — префикс), [math]s_{j+1}' \lt s_i'[/math] (по условию разбиения), [math]s_i' \lt s_i[/math] (их начало совпадает, и [math]|s_i| \lt |s_i'|[/math] по предположению. Получили противоречие: [math]s_i \lt s_i[/math].

2) Пусть [math]|s_i| \lt |s_i'|[/math] — проверяется аналогично.

То есть не может быть строк [math]s_i[/math] несовпадающей длины [math]\rightarrow[/math] разбиения равны.
[math]\triangleleft[/math]

Алгоритм Дюваля