Reconstructing a string from its Lyndon arrays

Jacqueline W. Daykin, Frantisek Franek, Jan Holub, A. S. M. Sohidull Islam, W. F. Smyth

Research output: Contribution to journalArticlepeer-review

11 Citations (SciVal)

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 = λ.
Original languageEnglish
Pages (from-to)44-51
Number of pages8
JournalTheoretical Computer Science
Volume710
Early online date02 May 2017
DOIs
Publication statusPublished - 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.

Cite this