کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952358 | 1364442 | 2016 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Fast computation of abelian runs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Given a word w and a Parikh vector P, an abelian run of period P in w is a maximal occurrence of a substring of w having abelian period P. Our main result is an online algorithm that, given a word w of length n over an alphabet of cardinality Ï and a Parikh vector P, returns all the abelian runs of period P in w in time O(n) and space O(Ï+p), where p is the norm of P, i.e., the sum of its components. We also present an online algorithm that computes all the abelian runs with periods of norm p in w in time O(np), for any given norm p. Finally, we give an O(n2)-time offline randomized algorithm for computing all the abelian runs of w. Its deterministic counterpart runs in O(n2logâ¡Ï) time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 656, Part B, 20 December 2016, Pages 256-264
Journal: Theoretical Computer Science - Volume 656, Part B, 20 December 2016, Pages 256-264
نویسندگان
Gabriele Fici, Tomasz Kociumaka, Thierry Lecroq, Arnaud Lefebvre, Ãlise Prieur-Gaston,