کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427735 | 686550 | 2012 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Quadratic-time algorithm for a string constrained LCS problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
The problem of finding a longest common subsequence of two main sequences with some constraint that must be a substring of the result (STR-IC-LCS) was formulated recently. It is a variant of the constrained longest common subsequence problem. As the known algorithms for the STR-IC-LCS problem are cubic-time, the presented quadratic-time algorithm is significantly faster.
► We investigate a string constrained LCS problem.
► We propose the first quadratic-time algorithm for the problem.
► We point out a flaw in some literature algorithm for the related problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 112, Issue 11, 15 June 2012, Pages 423–426
Journal: Information Processing Letters - Volume 112, Issue 11, 15 June 2012, Pages 423–426
نویسندگان
Sebastian Deorowicz,