TY - JOUR
T1 - Reconstructing a string from its Lyndon arrays
AU - Daykin, Jacqueline W.
AU - Franek, Frantisek
AU - Holub, Jan
AU - Islam, A. S. M. Sohidull
AU - Smyth, W. F.
PY - 2018/2/1
Y1 - 2018/2/1
N2 - 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 = λ.
AB - 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 = λ.
KW - Lyndon array
KW - Lyndon factorisation
KW - Lyndon word
KW - reverse engineering
KW - string reconstruction
U2 - 10.1016/j.tcs.2017.04.008
DO - 10.1016/j.tcs.2017.04.008
M3 - Article
SN - 0304-3975
VL - 710
SP - 44
EP - 51
JO - Theoretical Computer Science
JF - Theoretical Computer Science
ER -