Algorithms for Computing Abelian Periods of Words

Abstract

Constantinescu and Ilie (Bulletin EATCS 89, 167--170, 2006) introduced the notion of an \emph{Abelian period} of a word. A word of length $n$ over an alphabet of size $\sigma$ can have $\Theta (n^2)$ distinct Abelian periods. The Brute-Force algorithm computes all the Abelian periods of a word in time $O(n^2\times \sigma )$ using $O(n\times \sigma )$ space. We present an off-line algorithm based on a $\sel$ function having the same worst-case theoretical complexity as the Brute-Force one, but outperforming it in practice. We then present on-line algorithms that also enable to compute all the Abelian periods of all the prefixes of $w$.

Accepted for publication in Discrete Applied Mathematics

References in corpus (3)

• Algorithms for Jumbled Pattern Matching in Strings
• Binary Jumbled String Matching for Highly Run-Length Compressible Texts
• New algorithms for binary jumbled pattern matching

Cited by in corpus (4)

• Computing Abelian regularities on RLE strings
• Dyck Words, Lattice Paths, and Abelian Borders
• A Note on Easy and Efficient Computation of Full Abelian Periods of a Word
• On the Parikh-de-Bruijn grid