Изменения

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

1. Так как <tex>s < t</tex>, то <tex>\mathcal {9} exists i : s[i] < t[i]</tex> и <tex>s[j] = t[j]</tex>, <tex>j < i \rightarrow Rightarrow s + t < t</tex>

2. Пусть <tex>u</tex> {{---}} суффикс строки <tex>s + t</tex>. Тогда рассмотрим <tex> 3 </tex> возможных случая:

1) * <tex>|u| = |t| \rightarrow Rightarrow u = t \rightarrow Rightarrow u > s + t</tex> по пункту <tex> 1</tex>. 2) * <tex>|u| < |t| \rightarrow Rightarrow u</tex> {{---}} суффикс <tex>t</tex>. Так как <tex>t</tex> {{---}} простая, и <tex>t < u </tex> по определению <tex> \rightarrow Rightarrow s + t < t < u</tex> 3) * <tex>|u| > |t| \rightarrow Rightarrow s = s' + s''</tex>, <tex>u = s'' + t</tex>. Так как <tex>s</tex> {{---}} простая, <tex>s < s''</tex> и <tex>|s''| < |s| \rightarrow Rightarrow s + t < s'' + t</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 \geqslant s_2 \geqslant ... \geqslant s_k</tex>в котором меньше всего слов.Это конечный процессПокажем, так как длина что это и будет декомпозицией Линдона данной строки конечна <tex>\rightarrow</tex> получим нужное разбиение.

Пусть существует хотя бы одно разбиение строки на простые словаПредположим, что это не так.Возьмем разбиение строки на простые слова (без условия Значит, <tex>s_1 \geqslant s_2 \geqslant ... \geqslant s_kexists i : s_i < s_{i+1}</tex>) такое, чтобы . Так как слова <tex>ks_i </tex> было минимально.Пусть в нем есть и <tex>s_i < s_{i+1}</tex>простые, то из доказанной [[Декомпозиция Линдона#lemma | леммы]] следует, тогда что эти слова можно сконкатенировать и получить разбиение строки можно сконкатернировать <tex>\rightarrows </tex> получим разбиение с меньшим числом на меньшее число слов {{---}} . Получили противоречие с выбором <tex>k</tex>.

ПолучилиТаким образом доказали даже более сильное утверждение: <tex>s = s_1 s_2 ... s_k</tex>, <tex>k</tex> {{---}} минимально <tex>\Leftrightarrow</tex> нет <tex>s_i < s_{i+1}</tex>

Иначе <tex>\mathcal {9} exists s_i : |s_i| \neq |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 \leqslant < j</tex>.  Получаем: <tex>s_i < t</tex> (, так как <tex>s_i</tex> простая и по определению меньше своего суффикса),<tex>t < s_{j+1}'</tex> (так как <tex>t</tex> {{---}} префикс???),

2) Пусть Случай <tex>|s_i| < |s_i'|</tex> {{---}} проверяется аналогичносимметричен разобранному. То есть не может быть строк <tex>s_i</tex> несовпадающей длины <tex>\rightarrow</tex> , значит, разбиения равны.

Внешний цикл <tex>\mathrm{while}</tex> делает не более <tex>n</tex> итераций, поскольку в конце каждой его итерации к результату добавляется как минимум один символ (а всего символов <tex>n</tex>).

Оценим теперь количество итераций первого вложенного цикла <tex>\mathrm{while}</tex>. Для этого рассмотрим второй вложенный цикл <tex>\mathrm{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>\mathrm{while}</tex>, то этот цикл выполнит не более <tex>r \cdot p + p - 2</tex> итераций. Худшим случаем является случай <tex>r = 1</tex>, и мы получаем, что первый вложенный цикл <tex>\mathrm{while}</tex> всякий раз выполняет не более <tex>2p - 2</tex> итераций. Вспоминая, что всего выводится <tex>n</tex> символов, получаем, что для вывода <tex>n</tex> символов требуется не более <tex>2n - 2</tex> итераций первого вложенного <tex>\mathrm{while}</tex>. Следовательно, алгоритм Дюваля выполняется за <tex>O(n)</tex>.

Легко оценить и число сравнений символов, выполняемых алгоритмом Дюваля. Поскольку каждая итерация первого вложенного цикла <tex>\mathrm{while}</tex> производит два сравнения символов, а также одно сравнение производится после последней итерации цикла, то общее число сравнений символов не превосходит <tex>4n - 3</tex>.