Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

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.

[img]
Preview
PDF - Authors' Version
Download (230kB) | Preview
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.

Item Type: Journal Article
Murdoch Affiliation(s): 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

Downloads

Downloads per month over past year