Изменения
→Алгоритм Дюваля
Во время работы алгоритма строка <tex>s</tex> разделена на три строки <tex>s = s_1s_2s_3</tex>, где в строке <tex>s_1</tex> декомпозиция Линдона уже найдена и <tex>s_1</tex> уже больше не используется алгоритмом; строка <tex>s_2</tex> {{---}} это предпростая строка (причём длину простых строк внутри неё мы также запоминаем); строка <tex>s_3</tex> {{---}} это ещё не обработанная часть строки <tex>s</tex>. Алгоритм Дюваля берёт первый символ строки <tex>s_3</tex> и пытается дописать его к строке <tex>s_2</tex>. При этом, возможно, для какого-то префикса строки <tex>s_2</tex> декомпозиция Линдона становится известной, и эта часть переходит к строке <tex>s_1</tex>.
Будем поддерживаться указатель <tex>i</tex> на начало строки <tex>s_2</tex>. Внешний цикл алгоритма будет выполняться, пока <tex>i < n</tex>, то есть пока вся строка <tex>s</tex> не перейдёт в строку <tex>s_1</tex>. Внутри этого цикла создаются два указателя: указатель <tex>j</tex> на начало строки <tex>s_3</tex> и указатель <tex>k</tex> на текущий символ в строке <tex>s_2</tex>, с которым будет производиться сравнение. Затем будем в цикле пытаться добавить символ <tex>s[j]</tex> к строке <tex>s_2</tex>, для чего необходимо произвести сравнение с символом <tex>s[k]</tex>. Здесь у нас возникают три различных случаяПри этом будем поддерживать инвариант:<tex>j - k</tex> {{---}} длина подстроки w.
2. Если <tex>s[j] > s[k]</tex>, то, очевидно, строка <tex>s_2 + s[j]</tex> станет простой. Тогда мы увеличиваем <tex>j</tex> на единицу, а <tex>k</tex> передвигаем обратно на <tex>i</tex>, чтобы следующий символ сравнивался с первым символом <tex>s_2</tex>. То есть получаем новую простую строку длины <tex>j - k</tex>. 3. Если <tex>s[j] < s[k]</tex>, то строка <tex>s_2 + s[j]</tex> уже не может быть предпростой. Поэтому мы разбиваем предпростую строку <tex>s_2</tex> на простые строки плюс "остаток" (префикс простой строки, возможно, пустой); простые строки добавляем в ответ (т.е. выводим их позиции, попутно передвигая указатель <tex>i</tex>), а "остаток" вместе с символом <tex>s[j]</tex> переводим обратно в строку <tex>s_3</tex>, и останавливаем выполнение внутреннего цикла. Тем самым мы на следующей итерации внешнего цикла заново обработаем остаток, зная, что он не мог образовать предпростую строку с предыдущими простыми строками. Осталось только заметить, что при выводе позиций простых строк нам нужно знать их длину; но она, очевидно, равна <tex>j - k</tex>.
===Реализация===
===Корректность===
Покажем, что алгоритм получает нужное разложение. То есть все <tex>s_i</tex> - простые и <tex>s_1 \geqslant s_2 \geqslant ... \geqslant s_k</tex> лексикографически.
При обработке текущего символа в первом случае просто сдвигаем указатели, не записывая ответ. Во втором случае объединяем все найденные <tex>w</tex> с <tex>w'</tex> и получем новую строку <tex>w''</tex>.
Покажем, что <tex>w''</tex> является простой. Рассмотрим ее суффикс. Если он начинается в середине <tex>w</tex>, сравним его посимвольно со строкой <tex>s_2</tex>, и тогда в каком-то символе он окажется больше <tex>s_2</tex>, так как суффикс начинается с <tex>w</tex>, а строка <tex>w</tex> {{---}} простая и по определению меньше всех своих суффиксов. Если суффикс начинается в <tex>w'</tex>, то при сравнении расхождение будет в символах <tex>s[j]</tex> и <tex>s[k]</tex>. Но <tex>s[j] > s[k]</tex>, так что суффикс меньше <tex>w''</tex>. Если же суффикс начинается в начале <tex>w</tex>, отбросим общий префикс вида <tex>w + w + ... + w</tex> и придем к предыдущему случаю.
В третьем случае просто выведем все <tex>w</tex> и продолжим обработку со строки <tex>w'</tex>, так как при добавлении <tex>s[j] s_2</tex> перестанет удовлетворять требованиям, ведь в этом случае суффикс <tex>w'</tex> будет меньше <tex>w</tex>.
Теперь покажем, что <tex>s_i \geqslant s_{i + 1}</tex>.
Последоваельность из <tex>w</tex> будет удовлетворять условию, так как эти строки равны. Следующее слово будет иметь общий префикс с <tex>w</tex>, а после него будет стоять символ, меньший следующего символа из <tex>w</tex> (новое <tex>w</tex> получается по третьему случаю).
===Асимптотика===
