Слова Линдона. Декомпозиция Линдона: алгоритм нахождения декомпозиции Линдона за O(n).

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

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

Алфавит – конечное упорядоченное (лексикографически) множество символов.
Строка (слово) – конечная последовательность символов алфавита. Длина слова $w$ обозначается $|w|$.
Префикс слова $w$ – любая строка $u$ такая, что $w = uv$ для некоторого слова $v$ (возможно $u = w$ или $v = \varepsilon$).
Суффикс слова $w$ – любой $v$ такой, что $w = uv$ для некоторого слова $u$. Суффиксом может быть $w$ или пустое слово $\varepsilon$.
Циклический сдвиг (вращение) – слово, полученное из $w$ переносом первого символа $w$ в конец (или нескольких первых символов в конец). Например, вращениями $abac$ являются $abac, baca, acab, caba$.
Лексикографический порядок – задаётся порядком на алфавите; сравнение строк идёт посимвольно: строка $X$ лексикографически меньше $Y$ ($X < Y$), если на первой позиции, где они различаются, символ $X$ меньше символа $Y$, или если $X$ является собственным префиксом $Y$.
Слово Линдона – непустая строка $w$, которая строго лексикографически меньше любого своего нетривиального суффикса (или, эквивалентно, любого нетривиального циклического сдвига). Иными словами, $w$ – слово Линдона тогда и только тогда, когда $w < v$ для любого разбиения $w = uv$ с непустым $u$ и $v$. Например, строки $a$, $ab$, $aab$, $abb$, $ababb$ являются Линдон, а $aa$, $aba$ – не являются (так как $aa\ge a$, $aba > aa$). Любое слово Линдона апериодично (не является непустой степенью меньшего слова), поскольку, будучи единственным наименьшим вращением себя, оно не совпадает с каким-либо своим непустым циклическим сдвигом.
Простая (предпростая) строка – терминология варьируется, но часто «простая строка» означает то же, что слово Линдона. Можно также ввести понятие предпростая строки как $t = ww\cdots w w'$, где $w$ – простая строка, а $w'$ – её префикс (включая случай $w'=\varepsilon$). Это понятие используется при описании алгоритма.
Декомпозиция (факторизация) Линдона строки $s$ – представление $s=s_1 s_2 \cdots s_k$, где каждое $s_i$ – простое (Линдоново) слово, и при этом факторы упорядочены в невозрастающем лексикографическом порядке: $$s_1 \ge s_2 \ge \cdots \ge s_k.$$. По теореме Чен—Фокса—Линдона, такая разложение существует и единственно.

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

Апериодичность. Любое слово Линдона не является степенью меньшего слова. Иначе одно из нетривиальных вращений было бы меньше исходного слова, что противоречит определению. Это явно указано в литературе: слово Линдона «отличается от любого своего нетривиального вращения и, следовательно, апериодично».
Конкатенация двух Линдон слов. Если $s$ и $t$ – слова Линдона и $s < t$ (лексикографически), то их конкатенация $st$ также является словом Линдона. Более того, $st < t$. Это ключевая лемма, используемая при доказательстве существования и единственности факторизации: при наличии двух подряд стоящих Линдонов слов $s_i < s_{i+1}$ их можно сконкатенировать в более длинное простое слово.
Минимальный суффикс. При факторизации строки $s$ последним словом $s_k$ всегда является минимальным (лексикографически наименьшим) среди всех суффиксов $s$. Это следует из строения декомпозиции и доказательства алгоритма Дюваля.
Упорядоченность декомпозиции. В факторизации Линдона полученные слова упорядочены в невозрастающем порядке. Благодаря лемме (2) если бы $s_i < s_{i+1}$, то $s_i s_{i+1}$ было бы простым и разбиение имело бы меньше факторов, что противоречит минимальности числа факторов.
Теорема Чен—Фокса—Линдона: Любую строку можно единственным образом представить в виде конкатенации слов Линдона невозрастающей лексикографически последовательности. Эта теорема обеспечивает как существование, так и единственность разложения. Доказательство основано на выборе минимального по длине разбиения на простые слова и использовании леммы о конкатенации.

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

Алгоритм Дюваля строит декомпозицию Линдона строки $s$ (длины $n$) в один проход по строке. Он поддерживает разбиение строки на три части: $s = s_1 s_2 s_3$, где $s_1$ – уже обработанная и окончательная часть (факторы готовятся в выход), $s_2$ – текущее предпростое слово (в процессе наращивания), и $s_3$ – оставшаяся неразобранная часть. Алгоритм сдвигает границу между $s_2$ и $s_3$, постепенно добавляя символы к $s_2$, и при «нарушении простоты» выводит часть $s_2$ как один или несколько факторов.

Идея алгоритма:

Обходим строку слева направо с указателем $i$, обозначающим начало $s_2$.
Внутри каждой итерации поддерживаем два указателя: $j$ (начало нового символа в $s_3$) и $k$ (текущий символ в $s_2$ для сравнения). Изначально $j=i+1, k=i$.
Сравниваем символы $s[k]$ и $s[j]$:
Если $s[k] < s[j]$, то $s_2 + s[j]$ останется простым, поэтому сдвигаем $j \gets j+1$, а $k \gets i$ (начинаем сравнивать заново с началом $s_2$).
Если $s[k] = s[j]$, то продолжаем расширение: $s_2 + s[j]$ всё ещё предпростое, при этом делаем $k \gets k+1, j \gets j+1$ (наращиваем оба указателя).
Если $s[k] > s[j]$, то $s_2 + s[j]$ не может быть простым и мы завершили образование очередного Линдона. В этом случае на вывод идёт слово $w = s[i..\,j-k-1]$ длины $j-k$ (эту подстроку можно повторить $k-i+1$ раз, но алгоритм прямо выведет ее каждую копию). После этого устанавливаем $i \gets i + (j-k)$ и повторяем цикл заново.
Когда $j$ достигает конца строки ($j = n$), оставшуюся часть $s_2$ (которая по инварианту является простым словом) следует также вывести в качестве фактора.

Общую логику можно представить таким псевдокодом:

function LyndonFactorization(s):
 n ← length(s)
 i ← 0
 result ← empty list
 while i < n:
 j ← i + 1
 k ← i
 // Расширяем предпостощее слово
 while j < n and s[k] ≤ s[j]:
 if s[k] < s[j]:
 k ← i
 else:
 k ← k + 1
 j ← j + 1
 // Выводим фактор(-ы)
 while i ≤ k:
 result.append(s[i.. i + j - k - 1]) // вывод Lyndon-фактора
 i ← i + (j - k)
 return result

Этот код соответствует описанию в литературах по алгоритму Дюваля. На каждой итерации внешнего цикла мы находим максимально длинное простое (Линдоново) слово $w = s[i..\,i+j-k-1]$ и выводим его (в случае повторений – несколько копий подряд), затем смещаем $i$ на длину этого фактора и продолжаем.

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

Докажем, что алгоритм действительно находит декомпозицию Линдона: все выданные им факторы просты, и они расположены в невозрастающем лексикографическом порядке.

Простота выводимых факторов. По инварианту работы алгоритма в каждый момент подстрока $s_2 = s[i..\,k]$ является предпростой (предпростая строка). Алгоритм добавляет к ней символ $s[j]$ до тех пор, пока $s[k] ≤ s[j]$. Если на некотором шаге $s[k] > s[j]$, то строка $s_2 + s[j]$ перестаёт быть предпростой, что означает, что $w = s[i..\,j-k-1]$ (то, что мы выводим) является максимальной простой «секвенцией» внутри $s_2$. Формальное доказательство через анализ суффиксов показывает, что $w$ действительно меньше каждого своего собственного суффикса (см. части «Корректность» на неофициальном ресурсе). Таким образом, каждый выведенный фактор – Линдоново слово.
Невозрастающий порядок факторов. Пусть алгоритм последовательно выдал факторы $w*1, w*2, \ldots, w*k$. Покажем, что $w*1 \ge w*2 \ge \cdots \ge w*k$. Между выводом $w*i$ и $w*{i+1}$ алгоритм обнаруживает ситуацию $s[k] > s[j]$ и сдвигает $i$. Из леммы о конкатенации (см. раздел свойств) следует, что если бы $w*i < w*{i+1}$, то их конкатенация была бы простой, и алгоритм не остановился бы так рано. В более подробном анализе (см. доказательство корректности на ресурсе) показывается, что следующий после $w*i$ фактор либо совпадает с ним (в случае повторения), либо является его суффиксом меньшего символа – в любом случае не превосходит $w*i$.
Покрытие всей строки. Алгоритм перемещает границу $i$ на всю длину слова, постепенно разбирая $s_3$. Когда $i$ достигает $n$, вся строка разобрана. Суммарная длина выведенных факторов равна $n$.

Итак, алгоритм выводит декомпозицию $s = w*1 w*2 \cdots w*k$ такой, что каждое $w*i$ – Линдоново слово, и $w*1 \ge w*2 \ge \cdots \ge w*k$. Единственность такой факторизации гарантирована теоремой Чен–Фокса–Линдона.

Анализ сложности

Внешний цикл алгоритма выполняется не более $n$ итераций, поскольку при каждом выводе фактора указатель $i$ увеличивается хотя бы на 1. Работа алгоритма включает два вложенных цикла. Второй (вывода факторов) в сумме также выполняет не более $n$ итераций, так как каждый символ строки выводится ровно один раз. Главный трудоёмкий цикл – первый вложенный (сравнения $s[k] \le s[j]$). В литературе показано, что общее число сравнений не превосходит $2n-2$ в худшем случае, что дает линейную сложность. Формулировка на английском: «алгоритм имеет время $O(|w|)$ и $O(1)$ памяти». Таким образом, временная сложность алгоритма – $O(n)$. Память: алгоритм хранит лишь константное число указателей ($i,j,k$) и, возможно, выходной буфер под факторы. Дополнительная память, помимо входной строки и списка результатов, составляет $O(1)$.

Точное число сравнений и присваиваний зависит от структуры строки, но гарантируется линейный порядок. Например, алгоритм Дюваля (вариант с $O(1)$ памяти) делает не более $2n$ сравнений символов. Существуют и другие линейные варианты алгоритма (см. таблицу ниже).

Примеры и иллюстрации

Ниже приведены примеры разложений и пошаговый разбор нескольких случаев.

Таблица примеров декомпозиции Линдона. Для каждой строки указан результат работы алгоритма (разложение по словам Линдона):

Строка	Декомпозиция Линдона
`ababb`	`ababb`
`banana`	`b` · `an` · `an` · `a`
`abab`	`ab` · `ab`
`abracadabra`	`abracad` · `abr` · `a`
`abaabaab`	`ab` · `aab` · `aab`
`abababab`	`ab` · `ab` · `ab` · `ab`
`bbc`	`bbc`

Пример 1. Разбор строки “abaabaab”: алгоритм шаг за шагом (показаны индексы $i,j,k$ и результат сравнения):

Шаг	$i$	$j$	$k$	Сравнение	Действие
1	0	1	0	`s[0]`=`a` ≤ `s[1]`=`b`? (да, `a<b`)	$k=i=0$, $j=2$
2	0	2	0	`s[0]`=`a` ≤ `s[2]`=`a`? (да, =)	$k=1$, $j=3$
3	0	3	1	`s[1]`=`b` ≤ `s[3]`=`a`? (нет)	завершаем цикл расширения, выводим «`ab`» (от $i=0$ до $j-k-1=1$), $i=2$
4	2	3	2	`s[2]`=`a` ≤ `s[3]`=`a`? (да, =)	$k=3$, $j=4$
5	2	4	3	`s[3]`=`a` ≤ `s[4]`=`b`? (да, `a<b`)	$k=i=2$, $j=5$
6	2	5	2	`s[2]`=`a` ≤ `s[5]`=`a`? (да, =)	$k=3$, $j=6$
7	2	6	3	`s[3]`=`a` ≤ `s[6]`=`a`? (да, =)	$k=4$, $j=7$
8	2	7	4	`s[4]`=`b` ≤ `s[7]`=`b`? (да, =)	$k=5$, $j=8$ (конец)
9	2	8	5	–	выводим «`aab`» (от $i=2$ до $j-k-1=4$), $i=5$
10	5	8	5	–	выводим «`aab`» (от $i=5$ до $j-k-1=7$), $i=8$ (конец)

В результате: abaabaab = (ab)·(aab)·(aab).

Пример 2. Разбор строки “banana”:

$i=0$: $j=1,k=0$. Сравниваем s[0]='b' и s[1]='a'. Поскольку $b>a$, цикла расширения не было. Выводим фактор s[0..0]="b", устанавливаем $i=1$.
$i=1$: $j=2,k=1$. s[1]='a' ≤ s[2]='n' (да, $a<n$) → $k=1$, $j=3$.
s[1]='a' ≤ s[3]='a' (да, =) → $k=2$, $j=4$.
s[2]='n' ≤ s[4]='n' (да, =) → $k=3$, $j=5$.
s[3]='a' ≤ s[5]='a' (да, =) → $k=4$, $j=6$ (конец). Теперь выводим факторы: $i=1,k=4,j-k=2$, выводим s[1..2]="an", $i=3$; затем $i=3 \le 4$, выводим s[3..4]="an", $i=5$.
$i=5$: $j=6,k=5$ (начало нового расширения). Достигаем конца ($j=n$) без сравнения, выводим остаток s[5..5]="a". Итак: banana = (b)·(an)·(an)·(a).

В таблице ниже приведены результаты разложения для ряда примеров:

Строка	Разложение Линдона
`ababb`	`ababb`
`banana`	`b`·`an`·`an`·`a`
`abab`	`ab`·`ab`
`abracadabra`	`abracad`·`abr`·`a`
`abaabaab`	`ab`·`aab`·`aab`
`abababab`	`ab`·`ab`·`ab`·`ab`
`bbc`	`bbc`

Сравнение алгоритмов факторизации Линдона

Существуют различные алгоритмы для расчёта разложения Линдона, но классическим является алгоритм Дюваля. В таблице приведены основные варианты и их характеристики:

Алгоритм	Время	Доп. память	Число сравнений	Комментарии
Duval (1983, вариант 1)	$O(n)$	$O(1)$	≤ $2n-2$	Классический алгоритм Дюваля
Duval (1983, вариант 2)	$O(n)$	$O(n)$	≤ $1.5n$	Вариант Дюваля с $3n/2$ сравнений
Простая (наивная)	$O(n^2)$ (худ.)	$O(n)$	–	Сравниваем каждый суффикс
По суффиксному массиву	$O(n\log n)$	$O(n)$	–	Построение суффиксного массива + вывод
…	…	…	…	другие подходы (например, специализированные)*

Первый вариант алгоритма Дюваля делает не более $2n-2$ сравнений символов, второй – примерно $1.5n$. Обе версии линейны по времени; первый минимизирует память, второй – количество сравнений. Альтернативные методы (напр. на основе суффиксных структур) оказываются сложнее и обычно используют больше памяти.

Упражнения и вопросы

Найти декомпозицию Линдона. Для заданных строк найдите разложение: а) aababb; б) abcab; в) cbaabc; г) aaaa; д) bananaban. Решение:
aababb = (aababb) – само слово является Линдоном.
abcab = a·b·cab (проверить, что cab Линдоново).
cbaabc = c·ba·abc (каждый фактор меньше последующего).
aaaa = (a)·(a)·(a)·(a) (каждый символ сам по себе Линдоново).
bananaban = b·a·nanab·an (проверяется алгоритмом или вручную).
Проверка Линдоновости. Докажите или опровергните: слово Линдона обязательно апериодично. (Подсказка: рассуждение о вращениях.) Краткий ответ: да, апериодично, иначе существовал бы ненулевой сдвиг, оставляющий слово неизменным и делящий его на равные части, что бы нарушало условие быть наименьшим в ротации.
Вычисление минимального циклического сдвига. Объясните, как на основе декомпозиции Линдона найти позицию лексикографически минимального циклического сдвига строки. Подсказка: рассматривайте $s+s$ и разложение Дюваля – минимальный сдвиг начинается там, где фактор «пересекает» границу двух копий.
Доказательство линейности. Оцените число сравнений символов, выполняемых алгоритмом Дюваля, и обоснуйте сложность $O(n)$. Краткое решение: каждый внутренний цикл выполняет количество сравнений, суммарно не превосходящее $2n-2$, а вывод факторов – ещё $n$ операций.
Контрольные вопросы:
Что такое простое (Линдоново) слово?
Какую теорему формулирует Чен—Фокс—Линдон?
За какое время работает алгоритм Дюваля?
Почему в результате алгоритма факторы упорядочены невозрастающе?
Сколько дополнительной памяти требует алгоритм?

Ответы на контрольные вопросы фактически следуют из вышеизложенного материала. Например: (1) “простая строка” – определение из раздела «Определения»; (2) существует единственное разложение любой строки на Линдон слова; (3) и (5) – $O(n)$ времени и $O(1)$ памяти; (4) – см. раздел «Доказательство корректности».

Шаг	\(i\)	\(j\)	\(k\)	Сравнение	Действие
1	0	1	0	`s[0]`=`a` ≤ `s[1]`=`b`? (да, `a<b`)	\(k=i=0\), \(j=2\)
2	0	2	0	`s[0]`=`a` ≤ `s[2]`=`a`? (да, =)	\(k=1\), \(j=3\)
3	0	3	1	`s[1]`=`b` ≤ `s[3]`=`a`? (нет)	завершаем цикл расширения, выводим «`ab`» (от \(i=0\) до \(j-k-1=1\)), \(i=2\)
4	2	3	2	`s[2]`=`a` ≤ `s[3]`=`a`? (да, =)	\(k=3\), \(j=4\)
5	2	4	3	`s[3]`=`a` ≤ `s[4]`=`b`? (да, `a<b`)	\(k=i=2\), \(j=5\)
6	2	5	2	`s[2]`=`a` ≤ `s[5]`=`a`? (да, =)	\(k=3\), \(j=6\)
7	2	6	3	`s[3]`=`a` ≤ `s[6]`=`a`? (да, =)	\(k=4\), \(j=7\)
8	2	7	4	`s[4]`=`b` ≤ `s[7]`=`b`? (да, =)	\(k=5\), \(j=8\) (конец)
9	2	8	5	–	выводим «`aab`» (от \(i=2\) до \(j-k-1=4\)), \(i=5\)
10	5	8	5	–	выводим «`aab`» (от \(i=5\) до \(j-k-1=7\)), \(i=8\) (конец)

Алгоритм	Время	Доп. память	Число сравнений	Комментарии
Duval (1983, вариант 1)	\(O(n)\)	\(O(1)\)	≤ \(2n-2\)	Классический алгоритм Дюваля
Duval (1983, вариант 2)	\(O(n)\)	\(O(n)\)	≤ \(1.5n\)	Вариант Дюваля с \(3n/2\) сравнений
Простая (наивная)	\(O(n^2)\) (худ.)	\(O(n)\)	–	Сравниваем каждый суффикс
По суффиксному массиву	\(O(n\log n)\)	\(O(n)\)	–	Построение суффиксного массива + вывод
…	…	…	…	другие подходы (например, специализированные)*