Reconstructing a string from its Lyndon arrays

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

Allbwn ymchwil: Cyfraniad at gyfnodolynErthygladolygiad gan gymheiriaid

10 Dyfyniadau(SciVal)

Crynodeb

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 = λ.
Iaith wreiddiolSaesneg
Tudalennau (o-i)44-51
Nifer y tudalennau8
CyfnodolynTheoretical Computer Science
Cyfrol710
Dyddiad ar-lein cynnar02 Mai 2017
Dynodwyr Gwrthrych Digidol (DOIs)
StatwsCyhoeddwyd - 01 Chwef 2018

Ôl bys

Gweld gwybodaeth am bynciau ymchwil 'Reconstructing a string from its Lyndon arrays'. Gyda’i gilydd, maen nhw’n ffurfio ôl bys unigryw.

Dyfynnu hyn