Изменения

Возникают три различных случая:

* <tex>s[j] < s[k]:</tex> тогда строка <tex>s_2 + s[k]</tex> станет простой. Значит, мы увеличим <tex>k</tex> на единицу, а <tex>j</tex> передвигаем обратно на <tex>i</tex>, чтобы следующий символ сравнивался с первым символом <tex>s_2</tex>. То есть получаем новую простую строку длины <tex>k - j</tex>.

* <tex>s[j] > s[k]:</tex> значит, строка <tex>s_2 + s[k]</tex> уже не может быть предпростой. Добавляем к <tex> s_1 </tex> все строки <tex> w </tex>, а по нашему инварианту мы знаем, что их длина равна <tex> k - j </tex>, затем сдвигаем <tex> i </tex> к началу позиции строки <tex> w' </tex>. После чего внешний цикл запускаем заново: