Изменения

Покажем, что алгоритм получает нужное разложение. То есть все <tex>s_i</tex> {{- --}} простые , и <tex>s_1 \geqslant s_2 \geqslant ... \geqslant s_k</tex> лексикографически.

При обработке текущего символа в первом случае просто сдвигаем указатели, не записывая ответ. Во втором случае объединяем все найденные Мы сравниваем символы в <tex>w</tex> с и <tex>w'</tex> и получем новую строку на одинаковых позициях, а <tex>w''</tex>{{---}} префикс <tex> w </tex>, поэтому инвариант сохраняется.

Покажем, что Во втором случае объединяем все найденные <tex>w''</tex> является простой. Рассмотрим ее суффикс. Если он начинается в середине <tex>w</tex>, сравним его посимвольно со строкой <tex>s_2</tex>, и тогда в каком-то символе он окажется больше <tex>s_2</tex>, так как суффикс начинается с <tex>w</tex>, а строка <tex>w</tex> {{---}} простая и по определению меньше всех своих суффиксов. Если суффикс начинается в <tex>w'</tex>, то при сравнении расхождение будет в символах <tex>s[j]</tex> и <tex>s[k]</tex>. Но <tex>s[j] > s[k]</tex>, так что суффикс меньше получем новую строку <tex>w''</tex>. Если же суффикс начинается в начале <tex>w</tex>, отбросим общий префикс вида <tex>w + w + ... + w</tex> и придем к предыдущему случаю.

Покажем, что <tex>w''</tex> является простой. Рассмотрим ее суффикс. Если он начинается в середине <tex>w</tex>, сравним его посимвольно со строкой <tex>s_2</tex>, и тогда в каком-то символе он окажется больше <tex>s_2</tex>, так как суффикс <tex> w'' </tex> начинается с <tex> u </tex> {{---}} суффикса <tex>w</tex>, а строка <tex>w</tex> {{---}} простая и по определению меньше всех своих суффиксов. Если суффикс начинается в <tex>w'</tex>, то при сравнении расхождение будет в символах <tex>s[j]</tex> и <tex>s[k]</tex>. Но <tex>s[j] < s[k]</tex>, так что суффикс больше <tex>w''</tex>. Если же суффикс начинается с первой позиции какой-то подстроки <tex>w</tex>, то отбросим общий префикс вида <tex>w + w + ... + w</tex> и придем к предыдущему случаю.  В третьем случае просто выведем все <tex>w</tex> и продолжим обработку со строки <tex>w'</tex>, так как при добавлении <tex>s[jk] </tex>, <tex>s_2</tex> перестанет удовлетворять требованиям, ведь в этом случае суффикс строки <tex> s_2 </tex> равный <tex>w'</tex> будет меньше <tex>w</tex>.

Последоваельность из <tex>w</tex> будет удовлетворять условию, так как эти строки равны. Следующее слово будет иметь общий префикс с <tex>w</tex>, а после него будет стоять символ, меньший следующего символа из <tex>w</tex> (новое <tex>w</tex> получается по третьему случаю).