Изменения
→Алгоритм
}}
Во время работы алгоритма строка <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.
