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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 +
==Основные определения==
 
{{Определение
 
{{Определение
 
|id=def1.  
 
|id=def1.  
Строка 9: Строка 10:
 
}}
 
}}
  
 +
==Существование и единственность==
 
{{Лемма
 
{{Лемма
 
|id=lemma
 
|id=lemma
|statement=<tex>s </tex>,  <tex>t</tex> простые и  <tex>s < t</tex> лексикографически. Тогда:
+
|statement=<tex>s </tex>,  <tex>t</tex> {{---}} простые и  <tex>s < t</tex> лексикографически. Тогда:
 
1. <tex>s + t < t</tex>
 
1. <tex>s + t < t</tex>
 
2. <tex>s + t</tex> {{---}} простая  
 
2. <tex>s + t</tex> {{---}} простая  
Строка 17: Строка 19:
 
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| <= |t|</tex>
Пусть <tex>u</tex> суффикс строки <tex>s + t</tex>
+
Пусть <tex>u</tex> {{---}} суффикс строки <tex>s + t</tex>
  
 
1) <tex>|u| = |t| \rightarrow u = t \rightarrow u > s + t</tex>
 
1) <tex>|u| = |t| \rightarrow u = t \rightarrow u > s + t</tex>
  
2) <tex>|u| < |t| -> u</tex> {{---}} суффикс <tex>t</tex>. Так как <tex>t</tex> простая, <tex>t < u \rightarrow s + t < t < u</tex>
+
2) <tex>|u| < |t| -> u</tex> {{---}} суффикс <tex>t</tex>. Так как <tex>t</tex> {{---}} простая, <tex>t < u \rightarrow s + t < t < u</tex>
  
 
3) <tex>|u| > |t| \rightarrow s = s' + s''</tex>, <tex>u = s'' + t</tex>. Так как <tex>s</tex> {{---}} простая, <tex>s < s''</tex> и <tex>|s''| < |s| -> s + t < s'' + t</tex>
 
3) <tex>|u| > |t| \rightarrow s = s' + s''</tex>, <tex>u = s'' + t</tex>. Так как <tex>s</tex> {{---}} простая, <tex>s < s''</tex> и <tex>|s''| < |s| -> s + t < s'' + t</tex>
Строка 58: Строка 60:
 
То есть не может быть строк s_i несовпадающей длины \rightarrow разбиения равны.
 
То есть не может быть строк s_i несовпадающей длины \rightarrow разбиения равны.
 
}}
 
}}
 +
 +
==Алгоритм Дюваля==

Версия 21:46, 30 апреля 2014

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

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


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

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