# Reconstructing a string from its Lyndon arrays

Daykin, J.W., Franěk, F., Holub, J., Islam, A.S.M.S. and Smyth, W.F.
(2017)
*Reconstructing a string from its Lyndon arrays.*
Theoretical Computer Science, 710
.
pp. 44-51.

*Subscription may be required

## Abstract

Given a string x=x[1..n]x=x[1..n] on an ordered alphabet Σ of size σ , the Lyndon array λ=λx[1..n]λ=λx[1..n] of x is an array of positive integers such that View the MathML sourceλ[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ρ(n)<n, where ρ(n)ρ(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,…,λσ}λΣ={λ1=λ,λ2,…,λσ} corresponding to σ “rotations” of the alphabet can be used to determine uniquely the string x on Σ such that λx=λλx=λ.

Publication Type: | Journal Article |
---|---|

Murdoch Affiliation: | School of Engineering and Information Technology |

Publisher: | Elsevier BV |

Copyright: | © 2017 Elsevier B.V. |

URI: | http://researchrepository.murdoch.edu.au/id/eprint/37066 |

Item Control Page |