Ranking and unranking fixed-density necklaces and Lyndon words
2019; Elsevier BV; Volume: 791; Linguagem: Inglês
10.1016/j.tcs.2019.04.007
ISSN1879-2294
Autores Tópico(s)Advanced Combinatorial Mathematics
ResumoWe present the first polynomial-time ranking and unranking algorithms for fixed-density necklaces and Lyndon words. Using the unit-cost RAM model, the ranking algorithm runs in O(n3) time and the unranking algorithm runs in O(n4) time. By applying the ranking algorithms, the number of fixed-density necklaces and Lyndon words with a given prefix can also be computed in O(n3) time.
Referência(s)