Salta al contenuto principale
Passa alla visualizzazione normale.


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

  • Autori: Fici, G.; Lecroq, T.; Lefebvre, A.; Prieur-Gaston, É.; Smyth, W.
  • Anno di pubblicazione: 2016
  • Tipologia: Articolo in rivista (Articolo in rivista)
  • Parole Chiave: Abelian period; Abelian power; Combinatorics on words; Design of algorithms; Text algorithms; Weak repetition; Discrete Mathematics and Combinatorics; Applied Mathematics
  • OA Link:


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.