Изменения
Нет описания правки
Декомпозиция Линдона была изобретена Роджером Линдоном (англ. ''Roger Lyndon'') в 1954 году. Она используется для нахождения лексикографически минимального и максимального суффиксов строки.
==Основные определения==
{{Определение
|id=def1.
|definition='''Простая строка''' {{---}} строка, которая строго лексикографически меньше любого своего суффикса.
}}
Примеры:
<tex>ababb</tex> {{---}} простая строка, так как <tex>ababb < babb</tex>, <tex>ababb < abb</tex>, <tex>ababb < bb</tex>, <tex>ababb < b</tex>.
<tex>babaa</tex> {{---}} не простая строка, так как <tex>babaa > aa</tex>.
{{Определение
|id=def2.
|definition='''Декомпозиция Линдона''' (англ. ''Lyndon decomposition'') строки <tex>s</tex> {{---}} её разложение <tex>s = s_1 + s_2 + s_1s_2... + s_k</tex>, где строки <tex>s_i</tex> просты, и при этом <tex>s_1 \geqslant s_2 \geqslant ... \geqslant s_k</tex>.
}}
{{Лемма
|id=lemma
|statement=<tex>s </tex>, <tex>t</tex> {{---}} простые и <tex>s < t</tex> лексикографически. Тогдаверны следующие утверждения:
1. <tex>s + t < t</tex>
2. <tex>s + t</tex> {{---}} простая
|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>
2. Пусть <tex>u</tex> {{---}} суффикс строки <tex>s + t</tex> 1) <tex>|u| = |t| \rightarrow u = t \rightarrow u > s + t</tex>по пункту 1.
2) <tex>|u| < |t| \rightarrow 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| \rightarrow s + t < s'' + t</tex>
Пусть в нем есть <tex>s_i < s_{i+1}</tex>, тогда эти строки можно сконкатернировать <tex>\rightarrow</tex> получим разбиение с меньшим числом слов {{---}} противоречие с выбором <tex>k</tex>.
Получили: <tex>k</tex> {{---}} минимально <tex>\leftrightarrowLeftrightarrow</tex> нет <tex>s_i < s_{i+1}</tex>
2. Единственность.
Пусть существует несколько разбиений <tex>s = s_1 + s_2 + s_1s_2... + s_k = s_1' + s_2' + ... + s_k'</tex>,
удовлетворяющих условию теоремы.
Сравним длины первых двух слов <tex>s_1</tex> и <tex>s_1'</tex>, если <tex>|s_1| = |s_1'|</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 \leqslant j</tex>
Получаем: <tex>s_i < t</tex> (так как <tex>s_i</tex> простая и по определению меньше своего суффикса),
<tex>t < s_{j+1}'</tex> (так как <tex>t</tex> {{---}} префикс),
==Алгоритм Дюваля==
===Алгоритм===
Алгоритм Дюваля (англ. ''Duval's algorithm'') находит для данной строки длины <tex>n</tex> декомпозицию Линдона за время <tex>O(n)</tex> с использованием <tex>O(1)</tex> дополнительной памяти. Относится Он строит декомпозицию только на упорядоченных алфавитах. Алгоритм Дюваля относится к классу жадных алгоритмов.
{{Определение
|id=def3
|definition='''Предпростая строка''' {{---}} строка <tex>s</tex>, такая что <tex>s = w + w + ww... + w + www'</tex>, где <tex>w</tex> {{---}} некоторая простая строка, а <tex>w'</tex> {{- --}} некоторый префикс строки <tex>w</tex>.
}}
Во время работы алгоритма строка <tex>s</tex> разделена на три строки <tex>s = s_1 + s_2 + s_3s_1s_2s_3</tex>, где в строке <tex>s_1</tex> декомпозиция Линдона уже найдена и <tex>s_1</tex> уже больше не используется алгоритмом; строка <tex>s_2</tex> {{---}} это предпростая строка (причём длину простых строк внутри неё мы также запоминаем); строка <tex>s_3</tex> {{---}} это ещё не обработанная часть строки <tex>s</tex>. Алгоритм Дюваля берёт первый символ строки <tex>s_3</tex> и пытается дописать его к строке <tex>s_2</tex>. При этом, возможно, для какого-то префикса строки <tex>s_2</tex> декомпозиция Линдона становится известной, и эта часть переходит к строке <tex>s_1</tex>.
Будем поддерживаться указатель <tex>i</tex> на начало строки <tex>s_2</tex>. Внешний цикл алгоритма будет выполняться, пока <tex>i < n</tex>, то есть пока вся строка <tex>s</tex> не перейдёт в строку <tex>s_1</tex>. Внутри этого цикла создаются два указателя: указатель <tex>j</tex> на начало строки <tex>s_3</tex> и указатель <tex>k</tex> на текущий символ в строке <tex>s_2</tex>, с которым будет производиться сравнение. Затем будем в цикле пытаться добавить символ <tex>s[j]</tex> к строке <tex>s_2</tex>, для чего необходимо произвести сравнение с символом <tex>s[k]</tex>. Здесь у нас возникают три различных случая:
i <tex>\leftarrow</tex> 0
w <tex>\leftarrow</tex> 0
'''while''' (i < n) {
j <tex>\leftarrow</tex> i + 1
k <tex>\leftarrow</tex> i
'''while''' (j < n '''and ''' s[k] <= s[j]) {
'''if''' s[k] < s[j]
k <tex>\leftarrow</tex> i
j <tex>\leftarrow</tex> j + 1
}
'''while''' (i <= tex>\leqslant</tex> k) {
words[w] <tex>\leftarrow</tex> s[i..j-k]
w <tex>\leftarrow</tex> w + 1
Дополнительная память требуется только на три указателя: <tex>i, j, k</tex>.
Внешний цикл <tex>while </tex> делает не более <tex>n</tex> итераций, поскольку в конце каждой его итерации к результату добавляется как минимум один символ (а всего символов <tex>n</tex>).
Оценим теперь количество итераций первого вложенного цикла <tex>while</tex>. Для этого рассмотрим второй вложенный цикл <tex>while </tex> {{---}} он при каждом своём запуске выводит некоторое количество <tex>r \geqslant 1</tex> копий одной и той же простой строки некоторой длины <tex>p = j - k</tex>. Заметим, что строка <tex>s_2</tex> является предпростой, причём её простые строки имеют длину как раз <tex>p</tex>, т.е. её длина не превосходит <tex>r * \cdot p + p - 1</tex>. Поскольку длина строки <tex>s_2</tex> равна <tex>j - i</tex>, а указатель <tex>j</tex> увеличивается по единице на каждой итерации первого вложенного цикла <tex>while</tex>, то этот цикл выполнит не более <tex>r* \cdot p + p - 2</tex> итераций. Худшим случаем является случай <tex>r = 1</tex>, и мы получаем, что первый вложенный цикл <tex>while </tex> всякий раз выполняет не более <tex>2p - 2</tex> итераций. Вспоминая, что всего выводится <tex>n</tex> символов, получаем, что для вывода <tex>n</tex> символов требуется не более <tex>2n - 2</tex> итераций первого вложенного <tex>while</tex>. Следовательно, алгоритм Дюваля выполняется за <tex>O(n)</tex>.
Легко оценить и число сравнений символов, выполняемых алгоритмом Дюваля. Поскольку каждая итерация первого вложенного цикла <tex>while </tex> производит два сравнения символов, а также одно сравнение производится после последней итерации цикла, то общее число сравнений символов не превосходит <tex>4n - 3</tex>.
