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 wreiddiol | Saesneg |
---|---|
Tudalennau (o-i) | 44-51 |
Nifer y tudalennau | 8 |
Cyfnodolyn | Theoretical Computer Science |
Cyfrol | 710 |
Dyddiad ar-lein cynnar | 02 Mai 2017 |
Dynodwyr Gwrthrych Digidol (DOIs) | |
Statws | Cyhoeddwyd - 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.Proffiliau
-
Jacqueline Daykin
- Cyfadran Busnes a’r Gwyddorau Ffisegol, Cyfrifiadureg - Honorary Research Fellow
Unigolyn: Arall