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

Gabriele Fici, Élise Prieur-Gaston, Thierry Lecroq, William F. Smyth, Arnaud Lefebvre

Risultato della ricerca: Articlepeer review

3 Citazioni (Scopus)

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)-time algorithm for computing all the full Abelian periods of a word of length n over a constant-size alphabet. Experiments show that our algorithm significantly outperforms the O(n) algorithm proposed by Kociumaka et al. (2013) for the same problem.
Lingua originaleEnglish
pagine (da-a)88-95
Numero di pagine8
RivistaDiscrete Applied Mathematics
Volume212
Stato di pubblicazionePublished - 2016

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Entra nei temi di ricerca di 'A note on easy and efficient computation of full abelian periods of a word'. Insieme formano una fingerprint unica.

Cita questo