Изменения
→Алгоритм Дюваля
==Алгоритм Дюваля==
===Алгоритм===
Алгоритм Дюваля (англ. ''Duval's algorithm'') находит для данной строки длины <tex>n</tex> декомпозицию Линдона за время <tex>O(n)</tex> с использованием <tex>O(1)</tex> дополнительной памяти. Относится к классу жадных алгоритмов.
3. Если s[j] < s[k], то строка s_2 + s[j] уже не может быть предпростой. Поэтому мы разбиваем предпростую строку s_2 на простые строки плюс "остаток" (префикс простой строки, возможно, пустой); простые строки добавляем в ответ (т.е. выводим их позиции, попутно передвигая указатель i), а "остаток" вместе с символом s[j] переводим обратно в строку s_3, и останавливаем выполнение внутреннего цикла. Тем самым мы на следующей итерации внешнего цикла заново обработаем остаток, зная, что он не мог образовать предпростую строку с предыдущими простыми строками. Осталось только заметить, что при выводе позиций простых строк нам нужно знать их длину; но она, очевидно, равна j - k.
===Реализация===
string s // входная строка
string[] words // декомпозиция
}
}
===Асимптотика===
Дополнительная память требуется только на три указателя: 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.
