Изменения
→Алгоритм Дюваля
==Алгоритм Дюваля==
Алгоритм Дюваля (англ. ''Duval's algorithm'') находит для данной строки длины <tex>n</tex> декомпозицию Линдона за время <tex>O(n)</tex> с использованием <tex>O(1)</tex> дополнительной памяти. Относится к классу жадных алгоритмов.
{{Определение
|definition='''Предпростая строка''' {{---}} строка <tex>s</tex>, такая что <tex>s = w + w + ... + w + w'</tex>, где <tex>w</tex> {{---}} некоторая простая строка, а <tex>w'</tex> - некоторый префикс строки <tex>w</tex>.
}}
Во время работы алгоритма строка 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 // входная строка
