کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431042 | 688259 | 2011 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Finding the maximum suffix with fewer comparisons
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
It is shown how to compute the lexicographically maximum suffix of a string of n⩾2n⩾2 characters over a totally ordered alphabet using at most (4/3)n−5/3(4/3)n−5/3 three-way character comparisons. The best previous bound, which has stood unchallenged for more than 25 years, is (3/2)n−O(1)(3/2)n−O(1) comparisons. We also prove an interesting property of an algorithm for computing the maximum suffix both with respect to a total order < and with respect to its inverse order >.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 9, Issue 3, September 2011, Pages 279–286
Journal: Journal of Discrete Algorithms - Volume 9, Issue 3, September 2011, Pages 279–286
نویسندگان
Gianni Franceschini, Torben Hagerup,