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.
Fici, G., Lecroq, T., Lefebvre, A., Prieur-Gaston, É., Smyth, W. (2016). A note on easy and efficient computation of full abelian periods of a word. DISCRETE APPLIED MATHEMATICS, 212, 88-95 [10.1016/j.dam.2015.09.024].
A note on easy and efficient computation of full abelian periods of a word
FICI, Gabriele;
2016-01-01
Abstract
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.
| File | Dimensione | Formato | |
|---|---|---|---|
|
A note on easy and efficient computation of full abelian periods of a word.pdf
Solo gestori archvio
Dimensione
940.01 kB
Formato
Adobe PDF
|
940.01 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
