Декомпозиция Линдона

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

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

Определение:

Простая строка — строка, которая лексикографически меньше любого своего суффикса.

Примеры:

[math]ababb[/math] — простая строка, так как [math]ababb \lt babb[/math], [math]ababb \lt abb[/math], [math]ababb \lt bb[/math], [math]ababb \lt b[/math].

[math]babaa[/math] — не простая строка, так как [math]babaa \gt aa[/math].

Определение:

Декомпозиция Линдона (англ. Lyndon decomposition) строки [math]s[/math] — её разложение [math]s = s_1s_2...s_k[/math], где строки [math]s_i[/math] просты, и при этом [math]s_1 \geqslant s_2 \geqslant ... \geqslant 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]\exists i : s[i] \lt t[i][/math] и [math]s[j] = t[j][/math], [math]j \lt i \Rightarrow s + t \lt t[/math] 2. Пусть [math]u[/math] — суффикс строки [math]s + t[/math]. Тогда рассмотрим 3 возможных случая: [math]|u| = |t| \Rightarrow u = t \Rightarrow u \gt s + t[/math] по пункту 1 [math]|u| \lt |t| \Rightarrow u[/math] — суффикс [math]t[/math]. Так как [math]t[/math] — простая, и [math]t \lt u [/math] по определению [math] \Rightarrow s + t \lt t \lt u[/math] [math]|u| \gt |t| \Rightarrow s = s' + s''[/math], [math]u = s'' + t[/math]. Так как [math]s[/math] — простая, то её суффикс [math] s'' [/math] меньше самой строки [math] s [/math] в каком символе, значит, [math] s + t \lt s'' + t[/math]

[math]\triangleleft[/math]

Теорема (Чен-Линдон-Фокс):

Можно построить декомпозицию Линдона любой строки [math]s[/math], причем единственным образом.

Доказательство:

[math]\triangleright[/math]

1. Существование. У каждой строки существует хотя бы одно разбиение на простые слова. Это следует из того, что отдельный символ является простым словом. Тогда среди всех разбиений строки на простые слова возьмём то, в котором меньше всего слов. Покажем, что это и будет декомпозицией Линдона данной строки. Предположим, что это не так. Значит, [math]\exists i : s_i \lt s_{i+1}[/math]. Так как слова [math] s_i [/math] и [math] s_{i+1} [/math] простые, то из доказанной леммы следует, что эти слова можно сконкатенировать и получить разбиение строки [math] s [/math] на меньшее число слов. Получили противоречие. Таким образом доказали даже более сильное утверждение: [math]s = s_1 s_2 ... s_k[/math], [math] k [/math] — минимально [math]\Leftrightarrow[/math] нет [math]s_i \lt s_{i+1}[/math] 2. Единственность. Пусть существует несколько разбиений [math]s = s_1s_2...s_k = s_1's_2'...s_k'[/math], удовлетворяющих условию теоремы. Сравним длины первых двух слов [math]s_1[/math] и [math]s_1'[/math], если [math]|s_1| = |s_1'|[/math], сравним вторые и так далее. Если у всех слов длины одинаковы, то разбиения совпадают — противоречие. Иначе [math]\exists s_i : |s_i| \neq |s_i'|[/math]. Покажем, что такого не может быть: 1) Пусть [math]|s_i| \gt |s_i'|[/math], тогда [math]s_i = s_i's_{i+1}'...t[/math], где [math]t[/math] — префикс [math]s_{j+1}'[/math], [math]i \lt j[/math]. Тогда получаем: [math]s_i \lt t[/math] ([math]s_i[/math] — простая cтрока и по определению меньше своего суффикса) [math]t \lt s_{j+1}'[/math] ([math]t[/math] — префикс [math]s_{j+1}'[/math]) [math]s_{j+1}' \leqslant s_i'[/math] (по условию разбиения) [math]s_i' \lt s_i[/math] (их начало совпадает, и [math]|s_i| \lt |s_i'|[/math] по предположению) Пришли к противоречию: [math]s_i \lt s_i[/math]. 2) Случай [math]|s_i| \lt |s_i'|[/math] симметричен разобранному. То есть не может быть строк [math]s_i[/math] несовпадающей длины, значит, разбиения равны.

[math]\triangleleft[/math]

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

Алгоритм

Алгоритм Дюваля (англ. Duval's algorithm) находит для данной строки длины [math]n[/math] декомпозицию Линдона за время [math]O(n)[/math] с использованием [math]O(1)[/math] дополнительной памяти. Он строит декомпозицию только на упорядоченных алфавитах.

Определение:

Предпростая строка — строка [math]s[/math], такая что [math]s = ww \dots ww'[/math], где [math]w[/math] — некоторая простая строка, а [math]w'[/math] — некоторый префикс строки [math]w[/math].

Во время работы алгоритма строка [math]s[/math] представляется в виде конкатенации трёх строк [math]s = s_1s_2s_3[/math], где для строки [math]s_1[/math] декомпозиция Линдона уже найдена, и [math]s_1[/math] уже больше не используется алгоритмом; строка [math]s_2[/math] — это предпростая строка; строка [math]s_3[/math] — ещё не обработанная алгоритмом часть строки [math]s[/math]. Алгоритм Дюваля берёт первый символ строки [math]s_3[/math] и пытается дописать его к строке [math]s_2[/math]. При этом, возможно, для какого-то префикса строки [math]s_2[/math] декомпозиция Линдона становится известной, и эта часть переходит к строке [math]s_1[/math].

Будем поддерживать три указателя:

• [math]i[/math] — на начало строки [math]s_2[/math]
• [math]j[/math] — на текущий символ в строке [math]s_2[/math], с которым будет производиться сравнение
• [math]k[/math] — на начало строки [math]s_3[/math]

Внешний цикл алгоритма будет выполняться, пока [math]i \lt n[/math], то есть пока вся строка [math]s[/math] не перейдёт в строку [math]s_1[/math]. Внутри этого цикла создаются два указателя [math] j [/math] и [math] k [/math]. Затем будем пытаться добавить символ [math]s[k][/math] к строке [math]s_2[/math], для чего необходимо произвести сравнение с символом [math]s[j][/math]. При этом будем поддерживать инвариант: [math]k - j[/math] — длина подстроки [math] w [/math].

Возникают три различных случая:

• [math]s[j] = s[k]:[/math] тогда дописывыем символ [math]s[k][/math] к строке [math]s_2[/math].
• [math]s[j] \lt s[k]:[/math] тогда строка [math]s_2 + s[k][/math] станет простой. Значит, мы увеличим [math]k[/math] на единицу, а [math]j[/math] передвигаем обратно на [math]i[/math], чтобы следующий символ сравнивался с первым символом [math]s_2[/math]. То есть получаем новую простую строку длины [math]k - j[/math].
• [math]s[j] \gt s[k]:[/math] значит, строка [math]s_2 + s[k][/math] уже не может быть предпростой. Добавляем к [math] s_1 [/math] все строки [math] w [/math], а по нашему инварианту мы знаем, что их длина равна [math] k - j [/math], затем сдвигаем [math] i [/math] к началу позиции строки [math] w' [/math]. После чего внешний цикл запускаем заново:

Реализация

function lyndon(string s, string[] decomposition):
   n [math]\leftarrow[/math] |s|
   i [math]\leftarrow[/math] 0
   cur [math]\leftarrow[/math] 0
   while i [math] \lt  [/math] n:
       j [math]\leftarrow[/math] i
       k [math]\leftarrow[/math] i + 1
       while k [math] \lt  [/math] n and s[j] [math] \leqslant [/math] s[k]:
           if s[j] [math] \lt  [/math] s[k]:
               j [math]\leftarrow[/math] i
           else:
               j [math]\leftarrow[/math] k + 1
           k [math]\leftarrow[/math] k + 1
       while i [math]\leqslant[/math] j:
           decomposition[cur] [math]\leftarrow[/math] s[i..k - j]
           cur [math]\leftarrow[/math] cur + 1
           i [math]\leftarrow[/math] i + k - j

Корректность

Покажем, что алгоритм получает нужное разложение. То есть все [math]s_i[/math] — простые, и [math]s_1 \geqslant s_2 \geqslant ... \geqslant s_k[/math] лексикографически.

При обработке текущего символа в первом случае просто сдвигаем указатели, не записывая ответ. Мы сравниваем символы в [math] w [/math] и [math] w' [/math] на одинаковых позициях, а [math] w' [/math] — префикс [math] w [/math], поэтому инвариант сохраняется.

Во втором случае объединяем все найденные [math]w[/math] с [math]w'[/math] и получем новую строку [math]w''[/math].

Покажем, что [math]w''[/math] является простой. Рассмотрим ее суффикс. Если он начинается в середине [math]w[/math], сравним его посимвольно со строкой [math]s_2[/math], и тогда в каком-то символе он окажется больше [math]s_2[/math], так как суффикс [math] w'' [/math] начинается с [math] u [/math] — суффикса [math]w[/math], а строка [math]w[/math] — простая и по определению меньше всех своих суффиксов. Если суффикс начинается в [math]w'[/math], то при сравнении расхождение будет в символах [math]s[j][/math] и [math]s[k][/math]. Но [math]s[j] \lt s[k][/math], так что суффикс больше [math]w''[/math]. Если же суффикс начинается с первой позиции какой-то подстроки [math]w[/math], то отбросим общий префикс вида [math]w + w + ... + w[/math] и придем к предыдущему случаю.

В третьем случае просто выведем все [math]w[/math] и продолжим обработку со строки [math]w'[/math], так как при добавлении [math]s[k] [/math], [math]s_2[/math] перестанет удовлетворять требованиям, ведь в этом случае суффикс строки [math] s_2 [/math] равный [math] w'[/math] будет меньше [math]w[/math].

Теперь покажем, что [math]s_i \geqslant s_{i + 1}[/math].

Последоваельность из [math]w[/math] будет удовлетворять условию, так как эти строки равны. Следующее слово будет иметь общий префикс с [math]w[/math], а после него будет стоять символ, меньший следующего символа из [math]w[/math] (новое [math]w[/math] получается по третьему случаю).

Асимптотика

Дополнительная память требуется только на три указателя: [math]i, j, k[/math].

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

Оценим теперь количество итераций первого вложенного цикла [math]\mathrm{while}[/math]. Для этого рассмотрим второй вложенный цикл [math]\mathrm{while}[/math] — он при каждом своём запуске выводит некоторое количество [math]r \geqslant 1[/math] копий одной и той же простой строки некоторой длины [math]p = j - k[/math]. Заметим, что строка [math]s_2[/math] является предпростой, причём её простые строки имеют длину как раз [math]p[/math], т.е. её длина не превосходит [math]r \cdot p + p - 1[/math]. Поскольку длина строки [math]s_2[/math] равна [math]j - i[/math], а указатель [math]j[/math] увеличивается по единице на каждой итерации первого вложенного цикла [math]\mathrm{while}[/math], то этот цикл выполнит не более [math]r \cdot p + p - 2[/math] итераций. Худшим случаем является случай [math]r = 1[/math], и мы получаем, что первый вложенный цикл [math]\mathrm{while}[/math] всякий раз выполняет не более [math]2p - 2[/math] итераций. Вспоминая, что всего выводится [math]n[/math] символов, получаем, что для вывода [math]n[/math] символов требуется не более [math]2n - 2[/math] итераций первого вложенного [math]\mathrm{while}[/math]. Следовательно, алгоритм Дюваля выполняется за [math]O(n)[/math].

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