Lyndon word factorization

Question

Background

A Lyndon word is a non-empty string which is strictly lexicographically smaller than all its other rotations. It is possible to factor any string uniquely, by the Chen–Fox–Lyndon theorem, as the concatenation of Lyndon words such that these subwords are lexicographically non-increasing; your challenge is to do this as succinctly as possible.

Details

You should implement a function or program which enumerates the Lyndon word factorization of any printable ASCII string, in order, outputting the resultant substrings as an array or stream of some kind. Characters should be compared by their code points, and all standard input and output methods are allowed. As usual for code-golf, the shortest program in bytes wins.

Test Cases

''           []
'C'          ['C']
'aaaaa'      ['a', 'a', 'a', 'a', 'a']
'K| '        ['K|', ' ']
'abaca'      ['abac', 'a']
'9_-$'       ['9_', '-', '$']
'P&O(;'      ['P', '&O(;']
'xhya{Wd$'   ['x', 'hy', 'a{', 'Wd', '$']
'j`M?LO!!Y'  ['j', '`', 'M', '?LO', '!!Y']
'!9!TZ'      ['!9!TZ']
'vMMe'       ['v', 'MMe']
'b5A9A9<5{0' ['b', '5A9A9<5{', '0']

Answer 1

Pyth, 17 16 bytes

^{-1 byte thanks to isaacg!}

hf!ff>Y>YZUYT+./

Try it online!

Explanation

hf!ff>Y>YZUYT+./
              ./    Take all possible disjoint substring sets of [the input]
             +      plus [the input] itself (for the null string case).
 f                  Filter for only those sets which
  !f        T       for none of the substrings
    f  >YZUY        is there a suffix of the substring
     >Y             lexographically smaller than the substring itself.
h                   Return the first (i.e. the shortest) such set of substrings.

Answer 2

Jelly, 18 bytes

ṙJ¹ÐṂF⁼
ŒṖÇ€Ạ$ÐfṀȯ

Try it online!

Answer 3

Pyth - 28 bytes

hf&SI_T.Am.A>Rdt.u.>N1tddT./

Test Suite.

Answer 4

05AB1E, 15 bytes

.œé.Δεā<._ć›P}P

Try it online or verify all test cases.

Explanation:

.œ            # Get all partitions of the (implicit) input-string
  é           # Sort them by length
   .Δ         # Find the first/shortest which is truthy for:
     ε        #  Map over each part of the current partition:
      ā       #   Push a list in the range [1,length] (without popping the part-string)
       <      #   Decrease it to a 0-based range [0,length)
        ._    #   For each value, rotate the string that many times
          ć   #   Extract head; pop and push remainder-list and first item separately
              #   (where the head is the unmodified part-string)
           ›  #   Check for each rotated part if it's lexicographically larger than the
              #   unmodified part-string
            P #   Check whether this is truthy for all rotations
     }P       #  After the inner map: check whether it's truthy for all parts in the
              #  partition
              # (after which the found result is output implicitly as result)