Expert.
Put your skills to the test.

Problem summary

Split a lowercase string into consecutive simple words in nonincreasing lexicographic order. A word is simple when it is strictly smaller than every nonempty proper suffix. Print the number and lengths of the factors.

Constraints

String length≤1000000.

Worked example

Original statement sample.

baabaaabba

4 1 3 5 1

Solution analysis

1. A simple word is also called a Lyndon word. Duval’s algorithm maintains a candidate beginning at i, scans ahead with j, and compares against a position k inside the candidate. Equal characters extend a possible repetition; a larger new character resets k to i.
2. When the next character is smaller, the candidate cannot extend while preserving the Lyndon property. Its fundamental block length is j−k. Output that block repeatedly while its starting position is at most k, then begin the next candidate. This is why repeated patterns do not cause repeated rescanning of every suffix.
3. The sample factors are b | aab | aaabb | a, with lengths1,3,5,1. Each factor is smaller than its proper suffixes, and b≥aab≥aaabb≥a. A string of identical letters produces one-character factors; an increasing string such as abcd is one factor.

Why it works

During the inner scan, the examined prefix consists of repetitions of one Lyndon candidate followed by a prefix of it. A smaller next character fixes the candidate’s period and prevents it from extending. Emitting those copies produces the maximal first Lyndon factor(s), after which the same invariant applies to the remaining suffix. This is the Chen–Fox–Lyndon factorization, whose factors are nonincreasing.

Watch out. The comparison in the inner loop is ≤, while a strictly larger next character resets k. Reversing the inequalities computes a different factorization. Count repeated one-character factors individually.

An independently written complete program with standard headers.

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string text;
    cin>>text;
    int n=static_cast<int>(text.size());
    vector<int>lengths;
    int start=0;
    while(start<n){
        int scan=start+1;
        int matched=start;
        while(scan<n&&text[matched]<=text[scan]){
            if(text[matched]<text[scan]){
                matched=start;
            }
            else{
                matched++;
            }
            scan++;
        }
        int length=scan-matched;
        // Emit every completed repetition of this Lyndon block.
        while(start<=matched){
            lengths.push_back(length);
            start+=length;
        }
    }
    cout<<lengths.size();
    for(int length:lengths){
        cout<<' '<<length;
    }
    cout<<'\n';
}