Algorithms for computing Abelian periods of words ?
Constantinescu and Ilie [S. Constantinescu, L. Ilie. Fine and Wilfs theorem for abelian periods, Bulletin of the European Association for Theoretical Computer Science 89 (2006) 167170] introduced the notion of an Abelian period  of a word. A word of length n n over an alphabet of size ? ? can have ?(n2) ? ( n 2 ) distinct Abelian periods. The Brute-Force algorithm computes all the Abelian periods of a word in time O(n2?) O ( n 2  ? ) using O(n?) O ( n  ? ) space. We present an offline algorithm based on a select function having the same worst-case theoretical complexity as the Brute-Force one, but outperforming it in practice. We then present online algorithms that also enable us to compute all the Abelian periods of all the prefixes of w w .
abelian period abelian repetition weak repetition design of algorithms text algorithms combinatorics on words