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

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

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

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

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

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

Декомпозиция Линдона (англ. Lyndon decomposition) строки [math]s[/math] — её разложение [math]s = s_1 + s_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]\mathcal {9} 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]|s| \leqslant |t|[/math] Пусть [math]u[/math] — суффикс строки [math]s + t[/math] 1) [math]|u| = |t| \rightarrow u = t \rightarrow u \gt s + t[/math] 2) [math]|u| \lt |t| \rightarrow u[/math] — суффикс [math]t[/math]. Так как [math]t[/math] — простая, [math]t \lt u \rightarrow s + t \lt t \lt u[/math] 3) [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]s[i] \lt s[i+1][/math]. Так как символ — простая строка, по лемме [math]s[i..i+1][/math] — тоже простая и [math]s[i..i+1] \lt s[i][/math]. Далее склеиваем строки, не удовлетворяющие условию [math]s_1 \geqslant s_2 \geqslant ... \geqslant s_k[/math]. Это конечный процесс, так как длина строки конечна [math]\rightarrow[/math] получим нужное разбиение. Пусть существует хотя бы одно разбиение строки на простые слова. Возьмем разбиение строки на простые слова (без условия [math]s_1 \geqslant s_2 \geqslant ... \geqslant s_k[/math]) такое, чтобы [math]k[/math] было минимально. Пусть в нем есть [math]s_i \lt s_{i+1}[/math], тогда эти строки можно сконкатернировать [math]\rightarrow[/math] получим разбиение с меньшим числом слов — противоречие с выбором [math]k[/math]. Получили: [math]k[/math] — минимально [math]\leftrightarrow[/math] нет [math]s_i \lt s_{i+1}[/math] 2. Единственность. Пусть существует несколько разбиений [math]s = s_1 + s_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]\mathcal {9} 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 \leqslant 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]\rightarrow[/math] разбиения равны.

[math]\triangleleft[/math]

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

Алгоритм

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

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

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

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

Будем поддерживаться указатель i на начало строки s_2. Внешний цикл алгоритма будет выполняться, пока i < n, то есть пока вся строка s не перейдёт в строку s_1. Внутри этого цикла создаются два указателя: указатель j на начало строки s_3 и указатель k на текущий символ в строке s_2, с которым будет производиться сравнение. Затем будем в цикле пытаться добавить символ s[j] к строке s_2, для чего необходимо произвести сравнение с символом s[k]. Здесь у нас возникают три различных случая:

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

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

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

Реализация

   string s // входная строка
   string[] words // декомпозиция
   n [math]\leftarrow[/math] |s|
   i [math]\leftarrow[/math] 0
   w [math]\leftarrow[/math] 0
   while (i < n) {
   	j [math]\leftarrow[/math] i + 1
       k [math]\leftarrow[/math] i
   	while (j < n and s[k] <= s[j]) {
   	    if s[k] < s[j]
               k [math]\leftarrow[/math] i
           else
               k [math]\leftarrow[/math] k + 1
           j [math]\leftarrow[/math] j + 1
       }
       while (i <= k) {
           words[w] [math]\leftarrow[/math] s[i..j-k]
           w [math]\leftarrow[/math] w + 1
           i [math]\leftarrow[/math] i + j - k;
       }
   }

Асимптотика

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

Внешний цикл while делает не более n итераций, поскольку в конце каждой его итерации к результату добавляется как минимум один символ (а всего символов n).

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

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