Algorithms for computing Abelian periods of words

摘要

Constantinescu and Ilie [S. Constantinescu, L. Ilie. Fine and Wilf's theorem for abelian periods, Bulletin of the European Association for Theoretical Computer Science 89 (2006) 167-170] introduced the notion of an Abelian period of a word. A word of length n over an alphabet of size σ can have Θ(n~2) distinct Abelian periods. The Brute-Force algorithm computes all the Abelian periods of a word in time O(n~2 × σ) using 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.