Изменения

Во время работы алгоритма строка <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>j</tex> {{---}} на текущий символ в строке <tex>s_2</tex>, с которым будет производиться сравнение* <tex>k</tex> {{---}} на начало строки <tex>s_3</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[jk]</tex> к строке <tex>s_2</tex>, для чего необходимо произвести сравнение с символом <tex>s[kj]</tex>. При этом будем поддерживать инвариант: <tex>k - j - k</tex> {{---}} длина подстроки <tex> w</tex>.

1. Если * <tex>s[j] = s[k]:</tex>, то мы можем дописать тогда дописывыем символ <tex>s[jk]</tex> к строке <tex>s_2</tex>, не нарушив её "предпростоты". Следовательно, в этом случае мы просто увеличиваем указатели <tex>j</tex> и <tex>k</tex> на единицу, сохраняя инвариант. 2. Если * <tex>s[j] > < s[k]:</tex>, то, очевидно, тогда строка <tex>s_2 + s[jk]</tex> станет простой. Тогда Значит, мы увеличиваем увеличим <tex>jk</tex> на единицу, а <tex>kj</tex> передвигаем обратно на <tex>i</tex>, чтобы следующий символ сравнивался с первым символом <tex>s_2</tex>. То есть получаем новую простую строку длины <tex>k - j - k</tex>. 3. Если * <tex>s[j] < > s[k]:</tex>значит, то строка <tex>s_2 + s[jk]</tex> уже не может быть предпростой. Поэтому мы разбиваем предпростую строку Добавляем к <tex>s_2s_1 </tex> на простые строки плюс "остаток" (префикс простой строки, возможно, пустой); простые все строки добавляем в ответ (т.е. выводим их позиции, попутно передвигая указатель <tex>iw </tex>), а "остаток" вместе с символом по нашему инварианту мы знаем, что их длина равна <tex>s[k - j]</tex> переводим обратно в строку , затем сдвигаем <tex>s_3i </tex>, и останавливаем выполнение внутреннего цикла. Тем самым мы на следующей итерации внешнего цикла заново обработаем остаток, зная, что он не мог образовать предпростую строку с предыдущими простыми строками. Осталось только заметить, что при выводе позиций простых строк нам нужно знать их длину; но она равна к началу позиции строки <tex>j - kw' </tex>.После чего внешний цикл запускаем заново:

'''function''' lyndon('''string''' s <font color=green> // входная строка </font> , '''string[]''' words <font color=green> // декомпозиция </font>decomposition):

j <tex>\leftarrow</tex> i + 1 k <tex>\leftarrow</tex> i+ 1 '''while''' j k <tex> < </tex> n '''and''' s[kj] <tex> \leqslant </tex> s[jk]: '''if''' s[kj] <tex> < </tex> s[jk]: k j <tex>\leftarrow</tex> i

k j <tex>\leftarrow</tex> k + 1 j k <tex>\leftarrow</tex> j k + 1 '''while''' i <tex>\leqslant</tex> kj: wordsdecomposition[cur] <tex>\leftarrow</tex> s[i..k - j - k] cur <tex>\leftarrow</tex> w cur + 1 i <tex>\leftarrow</tex> i + k - j - k;