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. © Czech Technical University in Prague, Czech …