Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419151 | Discrete Applied Mathematics | 2014 | 11 Pages |
Abstract
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 nn over an alphabet of size σσ can have Θ(n2)Θ(n2) distinct Abelian periods. The Brute-Force algorithm computes all the Abelian periods of a word in time O(n2×σ)O(n2×σ) 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 ww.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Gabriele Fici, Thierry Lecroq, Arnaud Lefebvre, Élise Prieur-Gaston,