کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419151 | 681747 | 2014 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Algorithms for computing Abelian periods of words
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Algorithms for computing Abelian periods of words Algorithms for computing Abelian periods of words](/preview/png/419151.png)
چکیده انگلیسی
Constantinescu and Ilie [S. Constantinescu, L. Ilie. Fine and Wilf’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 nn over an alphabet of size σσ can have Θ(n2)Θ(n2) distinct Abelian periods. The Brute-Force algorithm computes all the Abelian periods of a word in time O(n2×σ)O(n2×σ) using O(n×σ)O(n×σ) 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 ww.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 163, Part 3, 30 January 2014, Pages 287–297
Journal: Discrete Applied Mathematics - Volume 163, Part 3, 30 January 2014, Pages 287–297
نویسندگان
Gabriele Fici, Thierry Lecroq, Arnaud Lefebvre, Élise Prieur-Gaston,