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

Декомпозиция Линдона была изобретена Роджером Линдоном (англ. 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]. Тогда рассмотрим [math] 3 [/math] возможных случая: [math]|u| = |t| \Rightarrow u = t \Rightarrow u \gt s + t[/math] по пункту [math] 1 [/math]. [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 \lt s''[/math] и [math]|s''| \lt |s| \Rightarrow 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] простая и по определению меньше своего суффикса, [math]t \lt s_{j+1}'[/math] (так как [math]t[/math] — префикс ???), [math]s_{j+1}' \lt 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...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]i \lt n[/math], то есть пока вся строка [math]s[/math] не перейдёт в строку [math]s_1[/math]. Внутри этого цикла создаются два указателя: указатель [math]j[/math] на начало строки [math]s_3[/math] и указатель [math]k[/math] на текущий символ в строке [math]s_2[/math], с которым будет производиться сравнение. Затем будем в цикле пытаться добавить символ [math]s[j][/math] к строке [math]s_2[/math], для чего необходимо произвести сравнение с символом [math]s[k][/math]. При этом будем поддерживать инвариант: [math]j - k[/math] — длина подстроки w.

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

1. Если [math]s[j] = s[k][/math], то мы можем дописать символ [math]s[j][/math] к строке [math]s_2[/math], не нарушив её "предпростоты". Следовательно, в этом случае мы просто увеличиваем указатели [math]j[/math] и [math]k[/math] на единицу, сохраняя инвариант.

2. Если [math]s[j] \gt s[k][/math], то, очевидно, строка [math]s_2 + s[j][/math] станет простой. Тогда мы увеличиваем [math]j[/math] на единицу, а [math]k[/math] передвигаем обратно на [math]i[/math], чтобы следующий символ сравнивался с первым символом [math]s_2[/math]. То есть получаем новую простую строку длины [math]j - k[/math].

3. Если [math]s[j] \lt s[k][/math], то строка [math]s_2 + s[j][/math] уже не может быть предпростой. Поэтому мы разбиваем предпростую строку [math]s_2[/math] на простые строки плюс "остаток" (префикс простой строки, возможно, пустой); простые строки добавляем в ответ (т.е. выводим их позиции, попутно передвигая указатель [math]i[/math]), а "остаток" вместе с символом [math]s[j][/math] переводим обратно в строку [math]s_3[/math], и останавливаем выполнение внутреннего цикла. Тем самым мы на следующей итерации внешнего цикла заново обработаем остаток, зная, что он не мог образовать предпростую строку с предыдущими простыми строками. Осталось только заметить, что при выводе позиций простых строк нам нужно знать их длину; но она равна [math]j - k[/math].

Реализация

   string s        // входная строка 
   string[] words  // декомпозиция 
   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 + 1
       k [math]\leftarrow[/math] i
       while j [math] \lt  [/math] n and s[k] [math] \leqslant [/math] s[j]:
           if s[k] [math] \lt  [/math] s[j]:
               k [math]\leftarrow[/math] i
           else:
               k [math]\leftarrow[/math] k + 1
           j [math]\leftarrow[/math] j + 1
       while i [math]\leqslant[/math] k:
           words[cur] [math]\leftarrow[/math] s[i..j - k]
           cur [math]\leftarrow[/math] w + 1
           i [math]\leftarrow[/math] i + j - k;

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

Покажем, что алгоритм получает нужное разложение. То есть все [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]s_2[/math], и тогда в каком-то символе он окажется больше [math]s_2[/math], так как суффикс начинается с [math]w[/math], а строка [math]w[/math] — простая и по определению меньше всех своих суффиксов. Если суффикс начинается в [math]w'[/math], то при сравнении расхождение будет в символах [math]s[j][/math] и [math]s[k][/math]. Но [math]s[j] \gt s[k][/math], так что суффикс меньше [math]w''[/math]. Если же суффикс начинается в начале [math]w[/math], отбросим общий префикс вида [math]w + w + ... + w[/math] и придем к предыдущему случаю.

В третьем случае просто выведем все [math]w[/math] и продолжим обработку со строки [math]w'[/math], так как при добавлении [math]s[j] 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].