A fast average case algorithm for lyndon decomposition

A simple algorithm, called LD, is described for computing the Lyndon decomposition of a word of length. Although LD requires time 0(n log n) in the worst case, it is shown to require only ®(rc) worst-case time for words which are “1-decomposable”, and ⊝(n) average-case time for words whose length is small with respect to alphabet size. The main interest in LD resides in its application to the problem of computing the canonical form of a …