کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
380226 1437427 2016 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Linear algorithm for conservative degenerate pattern matching
ترجمه فارسی عنوان
الگوریتم خطی برای تطبیق الگوی دژنراسیون محافظه کارانه
کلمات کلیدی
رشته تکاملی؛ تطبیق الگو؛ الگوریتم
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
چکیده انگلیسی

A degenerate symbol  x˜ over an alphabet Σ is a non-empty subset of Σ, and a sequence of such symbols is a degenerate string. A degenerate string is said to be conservative if its number of non-solid symbols is upper-bounded by a fixed positive constant k  . We consider here the matching problem of conservative degenerate strings and present the first linear-time algorithm that can find, for given degenerate strings P˜ and T˜ of total length n containing k   non-solid symbols in total, the occurrences of P˜ in T˜ in O(nk) time.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Engineering Applications of Artificial Intelligence - Volume 51, May 2016, Pages 109–114
نویسندگان
, , , , ,