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 longstanding 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 lineartime 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 lineartime 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 = λ.
Original language  English 

Pages (fromto)  4451 
Number of pages  8 
Journal  Theoretical Computer Science 
Volume  710 
Early online date  02 May 2017 
DOIs  
Publication status  Published  01 Feb 2018 
Keywords
 Lyndon array
 Lyndon factorisation
 Lyndon word
 reverse engineering
 string reconstruction
Fingerprint
Dive into the research topics of 'Reconstructing a string from its Lyndon arrays'. Together they form a unique fingerprint.Profiles

Jacqueline Daykin
 Faculty of Business and Physical Sciences, Department of Computer Science  Honorary Research Fellow
Person: Other