Reconstructing a string from its Lyndon arrays

Authors Organisations
  • Jacqueline Daykin(Author)
    King's College London
  • Frantisek Franek(Author)
    McMaster University
  • Jan Holub(Author)
    Czech Technical University
  • A. S. M. Sohidull Islam(Author)
    McMaster University
  • W. F. Smyth(Author)
    McMaster University
    King's College London
    Murdoch University
Type Article
Original languageEnglish
Pages (from-to)44-51
Number of pages8
JournalTheoretical Computer Science
Early online date02 May 2017
Publication statusPublished - 01 Feb 2018
Permanent link
View graph of relations
Citation formats


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


  • Lyndon array, Lyndon factorisation, Lyndon word, reverse engineering, string reconstruction