Слова Линдона. Декомпозиция Линдона: существование и единственность.

Краткое содержание: В этом обзоре излагаются определения и основные свойства слов Линдона – непустых строк над упорядоченным алфавитом, которые лексикографически строго меньше всех своих циклических сдвигов. Приводятся ключевые эквивалентные формулировки (например, сравнение с суффиксами или разбиениями слова) и указывается, что каждое слово Линдона апериодично (примитивно). Затем формулируется и доказывается теорема Чена–Фокса–Линдона о существовании и единственности раскладки произвольной строки в невозрастающую (лексикографически) последовательность слов Линдона. Следующим разделом описывается линейный алгоритм Дюваля (1983) для построения этого разложения, приводится его псевдокод, доказывается корректность и оценивается сложность O(n). В тексте имеются вспомогательные леммы, примеры раскладок и иллюстративная диаграмма. Приводится таблица-сравнение основных результатов (авторы, формулировки, условия, сложность). Отмечаются пограничные случаи и контрпримеры (например, условия на полный порядок алфавита). Все утверждения подкреплены цитатами из авторитетных источников.

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

Алфавит – конечное упорядоченное множество символов.
Слово (строка) над алфавитом – конечная (возможно пустая) последовательность символов. Длина слова w обозначается |w|.
Лексикографический порядок на строках: слово x считается меньшим слова y (x < y), если на позиции первого различия у них символ x[i] меньше y[i] по порядку алфавита, или x – префикс y.
Примитивное слово – конечное слово, не являющееся степенью некоторого более короткого слова. Формально, слово w называется примитивным, если не существует непустого u и числа k>1, что w = u^k. (Примитивное слово не обладает собственным периодом.)
Слово Линдона – непустое слово, которое лексикографически строго меньше всех своих нетривиальных циклических сдвигов (вращений). Иными словами, если w – слово Линдона длины n>0, то среди всех его сдвигов (рассмотренных как строки длины n) оно единственное минимально. Эквивалентная формулировка: слово w Линдона тогда и только тогда, когда оно непусто и строго меньше любого из своих собственных ненулевых суффиксов. Еще одно определение: если w=uv (где u,v≠ε), то в слове Линдона всегда u < v.

Примеры: над алфавитом {a<b}: a, b, ab, aab, abb, ababb, abcd и др. являются словами Линдона. Периодические слова (например, ababab) не являются словами Линдона, так как они равны некоторой степени более короткого слова. Заметим, что из определения следует, что любое слово Линдона апериодично (то есть примитивно): оно не совпадает ни с одним непустым собственным циклическим сдвигом.

Свойства слов Линдона

Лексикографически минимальное вращение: слово Линдона – минимум в лексикографическом порядке среди всех своих циклических перестановок.
Сравнение с суффиксами: в любом разбиении w=uv (u,v≠ε) для Линдона всегда u < v. Это равносильно предыдущему определению.
Апериодичность: слово Линдона не является степенью более короткого слова, т.е. оно примитивно.
Бесграни-ченность: у слова Линдона нет непустых собственных префикса, совпадающих с суффиксом (оно «беспогранично»). Это следует из его апериодичности.
Монотонность букв: если буквенный алфавит полностью упорядочен, то в слове Линдона каждая буква (кроме первой) не меньше предыдущей по лексикографическому порядку (поскольку префикс меньше суффикса при любом разбиении).
Порядок объединения: при конкатенации двух слов Линдона s и t, если s < t, то результат s+t также Линдоново (см. лемму ниже).

Все эти свойства легко проверить из определения и будут полезны при доказательстве теорем. Например, из определения следует, что любое слово Линдона меньше любого собственного суффикса и больше любого собственного префикса, а потому является примитивным.

Теорема о каноническом разложении (Chen–Fox–Lyndon)

Формулировка (Chen–Fox–Lyndon, 1958): Любая непустая строка над полностью упорядоченным алфавитом может быть единственным образом представлена в виде \(w = w*1 w*2 \cdots w*k\), где каждое \(w*i\) – слово Линдона, и они расположены в невозрастающем лексикографическом порядке \(w*1 \ge w*2 \ge \dots \ge w*k\).

В частности, это означает, что существует такое представление, и оно единственно. В англоязычной литературе это называется Lyndon factorization или Chen–Fox–Lyndon theorem. Нижеследующий текст иллюстрирует доказательство существования и единственности данного разложения.

Доказательство существования

Начало: любое слово s ненулевой длины можно разбить на символы-односимвольные слова (которые тривиально являются словами Линдона). Среди всех разбиений слова s на слова Линдона выберем разбиение с минимальным числом слагаемых. Пусть это \(s = s_1 s_2 \cdots s_k\), где каждое \(s_i\) – слово Линдона. По определению канонического разложения для него должно быть \(s_1 \ge s_2 \ge \dots \ge s_k\).
Анализ: предположим противное, что в этом минимальном разбиении найдется место i такое, что \(s_i < s_{i+1}\) (лексикографически). По лемме ниже получим, что конкатенация \(s_i s_{i+1}\) также является словом Линдона. Тогда строки \(s_i\) и \(s_{i+1}\) можно заменить единственным словом \(s_i s_{i+1}\), уменьшая число слагаемых разбиения, что противоречит минимальности \(k\).

Лемма: Если \(s\) и \(t\) – слова Линдона и \(s < t\), то \(s t\) – тоже слово Линдона и, к тому же, \(s t < t\). Доказательство леммы: Пользуясь \(s < t\) в лексикографическом порядке и свойством слов Линдона, проверяют все случаи сравнения \(s\) с \(t\) и получают, что конкатенация остается минимальной по сравнению с \(t\) и с любыми своими суффиксами (см. подробное доказательство в источнике).

Продолжая вывод, мы показали, что никакой пары \(s_i < s_{i+1}\) в минимальном разбиении быть не может. Значит, полученное разбиение уже удовлетворяет условию \(s_1 \ge s_2 \ge \dots \ge s_k\), то есть является стандартной факторизацией слова s.

Доказательство единственности

Пусть имеется два таких разложения одной и той же строки \(s\):

\[ s = s_1 s_2 \cdots s_k = s'_1 s'_2 \cdots s'_{\ell}, \]

где все \(s_i, s'_j\) – слова Линдона в невозрастающем порядке. Нужно показать, что эти последовательности совпадают. Сравним сначала первые слагаемые \(s_1\) и \(s'_1\). Если их длины равны, то по неубывающей упорядоченности и минимальности сравнения можно доказать, что фактически \(s_1 = s'_1\). Иначе, предположим без потери общности, что \(|s_i| > |s'_i|\) для некоторого i. Тогда \(s_i = s'_i u\) для некоторого непустого префикса \(u\) слова \(s'_{i+1}\). По свойству слов Линдона имеем \(s_i < u\) (так как \(s_i\) меньше любого своего суффикса) и \(u < s_{i+1}'\) (как префикс), а также \(s_{i+1}' \le s'_i\) (из невозрастания последовательности) и \(s'_i < s_i\) (начало совпадает, но \(s'_i\) короче). Скомбинировав эти неравенства, получаем \(s_i < s_i\), что невозможно. Аналогично рассматривается случай \(|s_i| < |s'_i|\), противоречие получается по симметрии. Следовательно, все \(s_i\) и \(s'_i\) по порядку совпадают, и разбиение единственно.

Таким образом, теорема о существовании и единственности стандартной факторизации слова доказана (см. детальную версию доказательства в источнике и ). Отметим, что условие упорядоченности алфавита необходимо для корректного определения лексикографического порядка и, соответственно, для постановки теоремы.

Алгоритм Дюваля (Duval’s Algorithm)

Жан-Пьер Дюваль (1983) предложил эффективный жадный алгоритм линейного времени для поиска описанной стандартной факторизации. Алгоритм проходит по строке слева направо, каждый раз находя самое длинное слово Линдона в текущей позиции.

Псевдокод (алгоритм Дюваля): пусть задано слово S длины n. Обозначим i = 0. Выполняем пока i < n:

j = i+1; k = i
while j < n и S[k] ≤ S[j]:
 if S[k] < S[j]:
 k = i
 else:
 k = k + 1
 j = j + 1
while i ≤ k:
 вывести фактор S[i.. i+(j-k)-1]
 i = i + (j - k)

Каждый раз, когда внутренний цикл заканчивается (когда либо j = n, либо встретилось S[k] > S[j]), длина фактора определяется как j - k. Этот фактор (подстрока S[i..i+j-k-1]) является очередным словом Линдона в разложении. После этого индекс i смещается вправо на j-k, и процесс повторяется. В итоге мы получаем последовательность Lyndon-слов, упорядоченных невозрастающе.

Корректность и сложность: В алгоритме Дюваля реализована жадная стратегия: всегда выбирается максимально длинный Lyndon-префикс оставшейся строки. Доказывается, что это приводит к стандартному разложению. Например, см. доказательство в e-maxx или другую трактовку. Важный факт: каждый символ строки обрабатывается константное число раз (внешний и внутренний циклы перемещают указатели вправо не более 4n раз общее). Итоговая сложность – \(O(n)\), дополнительная память – \(O(1)\) (кроме вывода).

Пример работы: Рассмотрим слово \(S = \texttt{banana}\). Алгоритм даст разложение

\[ \texttt{banana} = \texttt{b} + \texttt{an} + \texttt{an} + \texttt{a}, \]

где b ≥ an ≥ an ≥ a в лексикографическом порядке (действительно, 'b' > 'an' > 'a'). Действительно, при пошаговом выполнении: сначала выводится фактор "b", затем "an", потом ещё "an" и в конце "a". Проверка: ни один из этих фрагментов не имеет лексикографически меньшего собственного суффикса, так что все они слова Линдона. Другой пример: для \(S=\texttt{cabbage}\) алгоритм выдаёт c + abbage, потому что 'c' > 'abbage'. Такие примеры можно проверить с помощью приведённой реализации.

Таблица сравнения версий теорем и алгоритмов

Источник (авторы, год)	Условия	Суть результата	Сложность (алгоритм)
Shirshov (1953) / Lyndon (1954)	алфавит с полным порядком	введено понятие «стандартного лексикографического слова» (слова Линдона)	–
Chen–Fox–Lyndon (1958)	тот же	Любая строка имеет единственное разложение в невозрастающую последовательность слов Линдона	–
Duval (Jean-Pierre, 1983)	тот же	Алгоритм вычисления стандартного разложения слова Линдона; в статье доказана корректность	\(O(n)\) времени, \(O(1)\) доп. памяти

Строки таблицы отображают историю: Ширшов и Линдон впервые определили эти слова (1953–1954), затем Чен, Фокс и Линдон (1958) сформулировали и доказали теорему о разложении (существовании и единственности), а Дюваль (1983) предложил линейный алгоритм для фактического построения разложения.

Контрпримеры и замечания

Требование порядка алфавита: для постановки задачи необходим тотальный порядок символов в алфавите. Без него лексикографический критерий невозрастания потеряет смысл, и теорема не формулируется.
Пустая строка: часто не рассматривается, поскольку определение слова Линдона требует непустоты. Формально пустую строку можно разложить тривиально, но она не является Lyndon-словом.
Периодические слова: слово вида \(u^k\) (\(k>1\)) не является Lyndon-словом. Тем не менее, при факторизации любой периодической строки алгоритм разбивает её на минимальные Lyndon-факторы (например, \(\texttt{zzzz} = \texttt{z}+\texttt{z}+\texttt{z}+\texttt{z}\)).
Убывающий порядок: в факторизации важно, что последовательность Lyndon-слов лексикографически не возрастает (\(w*1 \ge w*2 \ge \dots\)). Иначе факторизация не единственна. Например, строку \(\texttt{aba}\) нельзя разложить как \(\texttt{a}+\texttt{ba}\), поскольку 'a' < 'ba' (это нарушало бы порядок). Алгоритм Дюваля гарантирует невозрастание.
Границы применимости: теорема верна для любых конечных слов над упорядоченными алфавитами. Обобщения на частично упорядоченные множества возможны, но требуют других формулировок (см. литературу).

Схема алгоритма Дюваля

Следующая диаграмма (Mermaid) иллюстрирует поток выполнения алгоритма Дюваля, находящего стандартное разложение строки:

flowchart TD A[Начало] --> B{i < n?} B -- Да --> C[j = i+1, k = i] C --> D{s[k] ≤ s[j]?} D -- "Да, & s[k] < s[j]" --> E[k = i; j++] D -- "Да, & s[k] = s[j]" --> F[k++; j++] D -- Нет --> G[Вывести фактор длины (j-k); i += (j-k)] E --> D F --> D G --> B B -- Нет --> H[Конец]

На диаграмме ветви отвечают за сравнение символов s[k] и s[j]: если s[k] ≤ s[j], продолжаем наращивать потенциальный Lyndon-блок; иначе фиксируем текущий Lyndon-фактор длины j-k и сдвигаем начало.