Prague Stringology Conference 2012

Gabriele Fici, Thierry Lecroq, Arnaud Lefebvre, Elise Prieur-Gaston and William F. Smyth

Quasi-linear Time Computation of the Abelian Periods of a Word

In the last couple of years many research papers have been devoted to Abelian complexity of words. Recently, Constantinescu and Ilie (Bulletin EATCS 89, 167–170, 2006) introduced the notion of Abelian period. In this article we present two quadratic brute force algorithms for computing Abelian periods for special cases and a quasi-linear algorithm for computing all the Abelian periods of a word.

Download paper: Article in PostScript Article in PDF BibTeX Reference
 PostScript   PDF   BibTeX reference