کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
428969 686978 2013 4 صفحه PDF سفارش دهید دانلود رایگان
عنوان انگلیسی مقاله ISI
A linear time algorithm for consecutive permutation pattern matching
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
سفارش ترجمه تخصصی
با تضمین قیمت و کیفیت
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A linear time algorithm for consecutive permutation pattern matching
چکیده انگلیسی


• We give a simple linear time algorithm for permutation consecutive pattern matching.
• Our algorithm is based on the Knuth–Morris–Pratt algorithm.
• This is the first algorithmic study of consecutive permutation patterns.

We say that two sequences x and w of length m   are order-isomorphic (of the same “shape”) if w[i]⩽w[j]w[i]⩽w[j] if and only if x[i]⩽x[j]x[i]⩽x[j] for each i,j∈[1,m]i,j∈[1,m]. We present a simple linear time algorithm for checking if a given sequence y of length n contains a factor which is order-isomorphic to a given pattern x. A factor is a subsequence of consecutive symbols of y  , so we call our problem the consecutive permutation pattern matching. The (general) permutation pattern matching problem is related to general subsequences and is known to be NP-complete. We show that the situation for consecutive subsequences is significantly different and present an O(n+m)O(n+m) time algorithm under a natural assumption that the symbols of x   can be sorted in O(m)O(m) time, otherwise the time is O(n+mlogm). In our algorithm we use a modification of the classical Knuth–Morris–Pratt string matching algorithm.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 113, Issue 12, 30 June 2013, Pages 430–433
نویسندگان
, , , , ,
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
سفارش ترجمه تخصصی
با تضمین قیمت و کیفیت