Reconstructing a string from its Lyndon arrays

Given a string x = x [ 1 . . n ] on an ordered alphabet Σ of size σ, the Lyndon array λ = λ x [ 1 . . n ] of x is an array of positive integers such that λ [ i ] , 1 ≤ i ≤ n , is the length of the maximal Lyndon word over the ordering of Σ that begins at position i in x . The Lyndon array has recently attracted considerable attention due to its pivotal role in establishing the long-standing conjecture that ρ ( n ) < n , where ρ ( n ) is the maximum number of maximal periodicities (runs) in any string of length n. Here we first describe two linear-time algorithms that, given a valid Lyndon array λ, compute a corresponding string — one for an alphabet of size n, the other for a smaller alphabet. We go on to describe another linear-time algorithm that determines whether or not a given integer array is a Lyndon array of some string. Finally we show how σ Lyndon arrays λ Σ = { λ 1 = λ , λ 2 , … , λ σ } corresponding to σ “rotations” of the alphabet can be used to determine uniquely the string x on Σ such that λ x = λ .