Constantinescu and Ilie (2006) introduced the idea of an Abelian period with head and tail of a finite word. An Abelian period is called full if both the head and the tail are empty. We present a simple and easy-to-implement O(nloglogn)-time algorithm for computing all the full Abelian periods of a word of length n over a constant-size alphabet. Experiments show that our algorithm significantly outperforms the O(n) algorithm proposed by Kociumaka et al. (2013) for the same problem.
|Number of pages||8|
|Journal||Discrete Applied Mathematics|
|Publication status||Published - 2016|
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Applied Mathematics