Journal article
A note on easy and efficient computation of full abelian periods of a word
Discrete Applied Mathematics, Vol.212, pp.88-95
2015
Abstract
Constantinescu and Ilie (2006) introduced the idea of an Abelian period with head and tail of a finite word. An Abelian period is called full if both the head and the tail are empty. We present a simple and easy-to-implement O(nloglogn)O(nloglogn)-time algorithm for computing all the full Abelian periods of a word of length nn over a constant-size alphabet. Experiments show that our algorithm significantly outperforms the O(n)O(n) algorithm proposed by Kociumaka et al. (2013) for the same problem.
Details
- Title
- A note on easy and efficient computation of full abelian periods of a word
- Authors/Creators
- G. Fici (Author/Creator) - University of PalermoT. Lecroq (Author/Creator) - Normandie UniversitéA. Lefebvre (Author/Creator) - Normandie UniversitéÉ. Prieur-Gaston (Author/Creator) - Normandie UniversitéW.F. Smyth (Author/Creator) - Murdoch University
- Publication Details
- Discrete Applied Mathematics, Vol.212, pp.88-95
- Publisher
- Elsevier BV
- Identifiers
- 991005542858407891
- Copyright
- © 2015 Published by Elsevier B.V.
- Murdoch Affiliation
- School of Engineering and Information Technology
- Language
- English
- Resource Type
- Journal article
Metrics
105 File views/ downloads
75 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
- Mathematics, Applied
- ESI research areas
- Engineering