Journal article
A linear partitioning algorithm for Hybrid Lyndons using -order
Theoretical Computer Science, Vol.483, pp.149-161
2013
Abstract
In this paper we extend previous work on unique maximal factorization families (UMFFs) and a total (but non-lexicographic) ordering of strings called VV-order. We present new combinatorial results for VV-order, in particular concatenation under VV-order. We propose linear-time RAM algorithms for string comparison in VV-order and for Lyndon-like factorization of a string into VV-words. This asymptotic efficiency thus matches that of the corresponding algorithms for lexicographical order. Finally, we introduce Hybrid Lyndon words as a generalization of standard Lyndon words, and hence propose extensions of factorization algorithms to other forms of order.
Details
- Title
- A linear partitioning algorithm for Hybrid Lyndons using -order
- Authors/Creators
- D.E. Daykin (Author/Creator) - University of ReadingJ.W. Daykin (Author/Creator) - Royal Holloway University of LondonW.F. Smyth (Author/Creator) - McMaster University
- Publication Details
- Theoretical Computer Science, Vol.483, pp.149-161
- Publisher
- Elsevier BV
- Identifiers
- 991005544892607891
- Copyright
- © 2012 Elsevier B.V.
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Journal article
Metrics
61 Record Views
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Collaboration types
- Domestic collaboration
- International collaboration
- Citation topics
- 4 Electrical Engineering, Electronics & Computer Science
- 4.182 Data Structures, Algorithms & Complexity
- 4.182.1103 Efficient Algorithms
- Web Of Science research areas
- Computer Science, Theory & Methods
- ESI research areas
- Computer Science