کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
433732 689618 2016 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Permuted scaled matching
ترجمه فارسی عنوان
تطبیق مدرج جایگشت
کلمات کلیدی
تطبیق الگو؛ تطبیق مدرج ؛ تطبیق چندپاره
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

Scaled matching and permutation matching are two well known paradigms in the domain of pattern matching. Scaled matching refers to finding an occurrence of a pattern which is enlarged proportionally by some scale k within a larger text. Permutation matching is the problem of finding all substrings within a text where the character statistics of the substring and the pattern are the same. Permutation matching is easy, while scaled matching requires innovative solutions. One interesting setting of applications is the merge of the two. The problem of scaled permuted matching (i.e. first permuting and then scaling) has been addressed and solved optimally. However, it was left as an open problem whether there are efficient algorithms for permuted scaled matching. In this paper we solve the problem efficiently in a deterministic setting and optimally in a randomized setting.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 638, 25 July 2016, Pages 27–32
نویسندگان
, , ,