Prague Stringology Conference 2012
Gabriele Fici, Thierry Lecroq, Arnaud Lefebvre, Elise Prieur-Gaston and William F. Smyth
Quasi-linear Time Computation of the Abelian Periods of a Word
| Abstract: |
| In the last couple of years many research papers have been devoted to Abelian complexity of words. Recently, Constantinescu and Ilie (Bulletin EATCS 89, 167–170, 2006) introduced the notion of Abelian period. In this article we present two quadratic brute force algorithms for computing Abelian periods for special cases and a quasi-linear algorithm for computing all the Abelian periods of a word. |
| Download paper: | |||
| PostScript | BibTeX reference |