Hintergrund

Ein Lyndon-Wort ist eine nicht leere Zeichenfolge, die streng lexikografisch kleiner ist als alle anderen Rotationen. Es ist möglich, jede Zeichenfolge als Verkettung von Lyndon-Wörtern eindeutig zu faktorisieren, sodass diese Unterwörter lexikografisch nicht ansteigen. Ihre Herausforderung besteht darin, dies so kurz wie möglich zu halten.

Einzelheiten

Sie sollten eine Funktion oder ein Programm implementieren, das die Lyndon-Wortfaktorisierung einer druckbaren ASCII-Zeichenfolge auflistet, um die resultierenden Teilzeichenfolgen als Array oder Stream auszugeben. Zeichen sollten anhand ihrer Codepunkte verglichen werden, und alle Standardeingabe- und -ausgabemethoden sind zulässig. Wie beim Code-Golf üblich , gewinnt das kürzeste Programm in Bytes.

Testfälle

''           []
'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']

Pyth, 17 16 Bytes

^{-1 Byte dank isaacg!}

hf!ff>Y>YZUYT+./

Probieren Sie es online aus!

Erläuterung

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.

Gelee , 18 Bytes

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

Probieren Sie es online aus!

Pyth - 28 Bytes

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

Testsuite .