Catalog Home Page

A note on easy and efficient computation of full abelian periods of a word

Fici, G., Lecroq, T., Lefebvre, A., Prieur-Gaston, É. and Smyth, W.F. (2015) A note on easy and efficient computation of full abelian periods of a word. Discrete Applied Mathematics, 212 . pp. 88-95.

Link to Published Version: http://dx.doi.org/10.1016/j.dam.2015.09.024
*Subscription may be required

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.

Publication Type: Journal Article
Murdoch Affiliation: School of Engineering and Information Technology
Publisher: Elsevier BV
Copyright: © 2015 Published by Elsevier B.V.
URI: http://researchrepository.murdoch.edu.au/id/eprint/29431
Item Control Page Item Control Page