کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950005 | 1440209 | 2016 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A note on easy and efficient computation of full abelian periods of a word
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: A note on easy and efficient computation of full abelian periods of a word A note on easy and efficient computation of full abelian periods of a word](/preview/png/4950005.png)
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 212, 30 October 2016, Pages 88-95
Journal: Discrete Applied Mathematics - Volume 212, 30 October 2016, Pages 88-95
نویسندگان
Gabriele Fici, Thierry Lecroq, Arnaud Lefebvre, Ãlise Prieur-Gaston, William F. Smyth,