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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Определение |id=def1. |definition='''Простая строка''' {{---}} строка, которая строго лексикографичес...»)
 
Строка 9: Строка 9:
 
}}
 
}}
  
−
Лемма. s, t – простые и s < t лексикографически. Тогда:
+
{{Лемма
−
1. s+t < t
+
|id=lemma
−
2. s + t – простая
+
|statement=<tex>s </tex>, <tex>t</tex> – простые и <tex>s < t</tex> лексикографически. Тогда:
−
Доказательство:
+
1. <tex>s + t < t</tex>
−
1. Так как s < t существует i : s[i] < t[i] и s[j] = t[j], j < I → s + t < t
+
2. <tex>s + t</tex> - простая  
−
2. |s| <= |t|
+
|proof=
−
Пусть u – суффикс строки s + t
+
1. Так как <tex>s < t</tex>, существует <tex>i : s[i] < t[i]</tex> и <tex>s[j] = t[j]</tex>, <tex>j < i</tex> -> <tex>s + t < t</tex>
−
1) |u| = |t| → u = t → u > s + t
+
2. <tex>|s| <= |t|</tex>
−
2) |u| < |t| → u – суффикс t. Так как t – простая, t < u → s + t < t < u
+
Пусть <tex>u</tex> – суффикс строки <tex>s + t</tex>
−
3) |u| > |t| → s = s' + s'', u = s'' + t. Так как s – простая, s < s'' и |s''| < |s| → s + t < s'' + t
 
  
−
Теорема. Можно построить декомпозицию Линдона любой строки s, причем единственным образом.
+
1) <tex>|u| = |t| -> u = t -> u > s + t</tex>
−
Доказательство:
+
 
 +
2) <tex>|u| < |t| -> u</tex> {{---}} суффикс <tex>t</tex>. Так как <tex>t</tex> – простая, <tex>t < u -> s + t < t < u</tex>
 +
 
 +
3) <tex>|u| > |t| -> s = s' + s''</tex>, <tex>u = s'' + t</tex>. Так как <tex>s</tex> {{---}} простая, <tex>s < s''</tex> и <tex>|s''| < |s| -> s + t < s'' + t</tex>
 +
}}
 +
 
 +
{{Теорема
 +
|id=theorem
 +
|statement=Можно построить декомпозицию Линдона любой строки s, причем единственным образом.
 +
|proof=
 
1. Существование.
 
1. Существование.
 
Разобьем строку на символы. Будем их склеивать, если подряд идущие символы: s[i] < s[i+1]. Так как символ - простая строка, по лемме s[i..i+1] - тоже простая и s[i..i+1] < s[i].
 
Разобьем строку на символы. Будем их склеивать, если подряд идущие символы: s[i] < s[i+1]. Так как символ - простая строка, по лемме s[i..i+1] - тоже простая и s[i..i+1] < s[i].
Строка 34: Строка 42:
  
 
2. Единственность.
 
2. Единственность.
−
      Пусть существует несколько разбиений s=s_1 + s_2 + … + s_k = s_1' + s_2' + … + s_k',
+
Пусть существует несколько разбиений s=s_1 + s_2 + … + s_k = s_1' + s_2' + … + s_k',
−
      удовлетворяющих условию теоремы.  
+
удовлетворяющих условию теоремы.  
 
Сравним длины первых двух слов s_1 и s_1', если |s_1| = |s_1'|, сравним вторые, и так далее.
 
Сравним длины первых двух слов s_1 и s_1', если |s_1| = |s_1'|, сравним вторые, и так далее.
 
Если у всех слов длины одинаковы, то разбиения совпадают!!!
 
Если у всех слов длины одинаковы, то разбиения совпадают!!!
Строка 49: Строка 57:
 
2) Пусть |s_i| < |s_i'| - проверяется аналогично.
 
2) Пусть |s_i| < |s_i'| - проверяется аналогично.
 
То есть не может быть строк s_i несовпадающей длины → разбиения равны.
 
То есть не может быть строк s_i несовпадающей длины → разбиения равны.
 +
}}

Версия 20:49, 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]i : s[i] \lt t[i][/math] и [math]s[j] = t[j][/math], [math]j \lt i[/math] -> [math]s + t \lt t[/math] 2. [math]|s| \lt = |t|[/math] Пусть [math]u[/math] – суффикс строки [math]s + t[/math]

1) [math]|u| = |t| -\gt u = t -\gt u \gt s + t[/math]

2) [math]|u| \lt |t| -\gt u[/math] — суффикс [math]t[/math]. Так как [math]t[/math] – простая, [math]t \lt u -\gt s + t \lt t \lt u[/math]

3) [math]|u| \gt |t| -\gt 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]
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Декомпозиция_Линдона&oldid=36508»