کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874791 | 688036 | 2014 | 20 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Extending common intervals searching from permutations to sequences
ترجمه فارسی عنوان
گسترش فواصل زمانی جستجو از طریق تعویض به دنباله
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper, we propose to characterize the structure of a sequence by the number q of different dominating orders composing it (called the domination number), and to use a recent algorithm for permutations in order to devise a new algorithm for two sequences. Its running time is in O(q1q2p+q1n1+q2n2+N), where n1, n2 are the sizes of the two sequences, q1, q2 are their respective domination numbers, p is the alphabet size and N is the number of solutions to output. This algorithm performs better as q1 and/or q2 reduce, and when the two sequences are reduced to permutations (i.e. when q1=q2=1) it has the same running time as the best algorithms for permutations. It is also the first algorithm for sequences whose running time involves the parameter size of the solution. As a counterpart, when q1 and q2 are of O(n1) and O(n2) respectively, the algorithm is less efficient than other approaches.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 29, November 2014, Pages 27-46
Journal: Journal of Discrete Algorithms - Volume 29, November 2014, Pages 27-46
نویسندگان
Irena Rusu,