دانلود مقاله ISI انگلیسی شماره 79717
عنوان فارسی مقاله

یک الگوریتم برنامه نویسی پویا کارآمد برای مشکل LCS تعمیم با رشته های متعدد محدودیت منحصر به فرد

کد مقاله سال انتشار مقاله انگلیسی ترجمه فارسی تعداد کلمات
79717 2014 8 صفحه PDF سفارش دهید محاسبه نشده
خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.
عنوان انگلیسی
An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Journal of Discrete Algorithms, Volume 26, May 2014, Pages 98–105

کلمات کلیدی
برنامه نویسی پویا؛ الگوریتم؛ مشکل LCS تعمیم یافته؛ خروج رشته های متعدد
پیش نمایش مقاله
پیش نمایش مقاله یک الگوریتم برنامه نویسی پویا کارآمد برای مشکل LCS تعمیم با رشته های متعدد محدودیت منحصر به فرد

چکیده انگلیسی

In this paper, we consider a generalized longest common subsequence problem with multiple substring exclusive constraints. For the two input sequences X and Y of lengths n and m, and a set of d   constraints P={P1,…,Pd}P={P1,…,Pd} of total length r, the problem is to find a common subsequence Z of X and Y excluding each of constraint string in P as a substring and the length of Z is maximized. The problem was declared to be NP-hard [7], but we finally found that this is not true. A new dynamic programming solution for this problem is presented in this paper. The correctness of the new algorithm is proved. The time complexity of our algorithm is O(nmr)O(nmr).

خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.