Reconstructing a string from its Lyndon arrays

• DOI: 10.1016/j.tcs.2017.04.008
• Publication Date: 2017-05-02T16:47:32Z
• Authors: Jacqueline W. Daykin; Frantisek Franek; Jan Holub; A.S.M. Sohidull I...; W.F. Smyth
• Keywords: 0102 computer and information sciences; 01 natural sciences

Abstract 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 = λ .