Изменения

Во время работы алгоритма строка <tex>s </tex> разделена на три строки <tex>s = s_1 + s_2 + s_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>. Здесь у нас возникают три различных случая:

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

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>.

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>i, j, k</tex>.

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

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

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