Algorithms for computing Abelian periods of words

作者：Fici Gabriele^*; Lecroq Thierry; Lefebvre Arnaud; Prieur Gaston Elise

来源：Discrete Applied Mathematics, 2014, 163: 287-297.

DOI：10.1016/j.dam.2013.08.021

• Abelian period
• Abelian repetition
• Weak repetition
• Design of algorithms
• Text algorithms
• Combinatorics on words

Constantinescu and file [S. Constantinescu, L. Hie. Fine and Wilt%26apos;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 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) x sigma) using O(n x sigma) 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.

• 出版日期2014-1-30