Reconstructing a string from its Lyndon arrays
| Autor: | Frantisek Franek, Jacqueline W. Daykin, A. S. M. Sohidull Islam, William F. Smyth, Jan Holub |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Discrete mathematics
Conjecture General Computer Science String (computer science) 0102 computer and information sciences 02 engineering and technology 01 natural sciences Theoretical Computer Science Lyndon words Combinatorics Integer 010201 computation theory & mathematics Position (vector) 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Alphabet Mathematics |
| Zdroj: | Theoretical Computer Science. 710:44-51 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2017.04.008 |
| Popis: | 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 = λ . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect