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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Основные определения)
(Существование и единственность)
Строка 18: Строка 18:
 
|proof=
 
|proof=
 
1. Так как <tex>s < t</tex>, <tex>\mathcal {9} i : s[i] < t[i]</tex> и <tex>s[j] = t[j]</tex>, <tex>j < i \rightarrow s + t < t</tex>
 
1. Так как <tex>s < t</tex>, <tex>\mathcal {9} i : s[i] < t[i]</tex> и <tex>s[j] = t[j]</tex>, <tex>j < i \rightarrow s + t < t</tex>
2. <tex>|s| <= |t|</tex>
+
2. <tex>|s| \leqslant |t|</tex>
 
Пусть <tex>u</tex> {{---}} суффикс строки <tex>s + t</tex>
 
Пусть <tex>u</tex> {{---}} суффикс строки <tex>s + t</tex>
  
Строка 35: Строка 35:
  
 
Разобьем строку на символы. Будем их склеивать, если подряд идущие символы: <tex>s[i] < s[i+1]</tex>. Так как символ {{---}} простая строка, по лемме <tex>s[i..i+1]</tex> {{---}} тоже простая и <tex>s[i..i+1] < s[i]</tex>.
 
Разобьем строку на символы. Будем их склеивать, если подряд идущие символы: <tex>s[i] < s[i+1]</tex>. Так как символ {{---}} простая строка, по лемме <tex>s[i..i+1]</tex> {{---}} тоже простая и <tex>s[i..i+1] < s[i]</tex>.
Далее склеиваем строки, не удовлетворяющие условию <tex>s_1 >= s_2 >= ... >= s_k</tex>.
+
Далее склеиваем строки, не удовлетворяющие условию <tex>s_1 \geqslant s_2 \geqslant ... \geqslant s_k</tex>.
 
Это конечный процесс, так как длина строки конечна <tex>\rightarrow</tex> получим нужное разбиение.
 
Это конечный процесс, так как длина строки конечна <tex>\rightarrow</tex> получим нужное разбиение.
  
 
Пусть существует хотя бы одно разбиение строки на простые слова.
 
Пусть существует хотя бы одно разбиение строки на простые слова.
Возьмем разбиение строки на простые слова (без условия  <tex>s_1 >= s_2 >= ... >= s_k</tex>) такое, чтобы <tex>k</tex> было минимально.
+
Возьмем разбиение строки на простые слова (без условия  <tex>s_1 \geqslant s_2 \geqslant ... \geqslant s_k</tex>) такое, чтобы <tex>k</tex> было минимально.
 
Пусть в нем есть <tex>s_i < s_{i+1}</tex>, тогда эти строки можно сконкатернировать <tex>\rightarrow</tex> получим разбиение с меньшим числом слов {{---}} противоречие с выбором <tex>k</tex>.
 
Пусть в нем есть <tex>s_i < s_{i+1}</tex>, тогда эти строки можно сконкатернировать <tex>\rightarrow</tex> получим разбиение с меньшим числом слов {{---}} противоречие с выбором <tex>k</tex>.
  
Строка 54: Строка 54:
  
 
1) Пусть <tex>|s_i| > |s_i'|</tex>
 
1) Пусть <tex>|s_i| > |s_i'|</tex>
Тогда <tex>s_i = s_i' + s_{i+1}' + ... + t</tex>, где <tex>t</tex> {{---}} префикс <tex>s_{j+1}'</tex>, <tex>i <= j</tex>
+
Тогда <tex>s_i = s_i' + s_{i+1}' + ... + t</tex>, где <tex>t</tex> {{---}} префикс <tex>s_{j+1}'</tex>, <tex>i \leqslant j</tex>
 
Получаем: <tex>s_i < t</tex> (так как <tex>s_i</tex> простая и по определению меньше своего суффикса),
 
Получаем: <tex>s_i < t</tex> (так как <tex>s_i</tex> простая и по определению меньше своего суффикса),
 
<tex>t < s_{j+1}'</tex> (так как <tex>t</tex> {{---}} префикс),
 
<tex>t < s_{j+1}'</tex> (так как <tex>t</tex> {{---}} префикс),

Версия 22:12, 30 апреля 2014

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

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


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

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