کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952351 | 1364442 | 2016 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Two fast constructions of compact representations of binary words with given set of periods
ترجمه فارسی عنوان
دو ساختار سریع نمایه های جمع و جور کلمات باینری با مجموعه ای از دوره های داده شده
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
دوره ای سیستم کلاژ الگوریتم، مرز ها،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Assume we are given a sorted set P of size n of all periods of an unknown string of size N. Our main result is an algorithm generating in O(n) time and O(1) space a compressed representation of size O(n) of the lexicographically-first binary string having P as the set of its periods. The input is read-only and the output is write-only. We also present a very simple preliminary algorithm generating some binary string (not necessarily lexicographically-first one) with the same set of periods. The explicit size N of the produced string can be exponential with respect to n. We assume that a given set of periods is valid: there exists some unknown string realizing this set.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 656, Part B, 20 December 2016, Pages 180-187
Journal: Theoretical Computer Science - Volume 656, Part B, 20 December 2016, Pages 180-187
نویسندگان
Wojciech Rytter,