Algorithms to compute the lyndon array

In the Lyndon array λ = λx[1.n] of a string x = x[1.n], λ[i] is the length of the longest Lyndon word starting at position i of x. The computation of λ has recently become of great interest, since it was shown (Bannai et al., The "Runs" Theorem) that the runs in x are computable in linear time from λx. Here we describe two algorithms for computing λx based on previous results known in different context, but for which no explicit exposition in …