کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950835 | 1441037 | 2017 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Finding the largest fixed-density necklace and Lyndon word
ترجمه فارسی عنوان
پیدا کردن بزرگترین گردنبند چگالی ثابت و کلمه لیندون
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم ها، گردنبند، کلمه لیندون، چگالی ثابت رتبه بندی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We present an O(n) time algorithm for finding the lexicographically largest fixed-density necklace of length n. Then we determine whether or not a given string can be extended to a fixed-density necklace of length n in O(n2) time. Finally, we give an O(n3) algorithm that finds the largest fixed-density necklace of length n that is less than or equal to a given string. The efficiency of the latter algorithm is a key component to allow fixed-density necklaces to be ranked efficiently. The results are extended to find the largest fixed-density Lyndon word of length n (that is less than or equal to a given string) in O(n3) time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 125, September 2017, Pages 15-19
Journal: Information Processing Letters - Volume 125, September 2017, Pages 15-19
نویسندگان
Joe Sawada, Patrick Hartman,