کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
436981 690059 2012 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Parameterized searching with mismatches for run-length encoded strings
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Parameterized searching with mismatches for run-length encoded strings
چکیده انگلیسی

Parameterized matching between two strings occurs when it is possible to reduce the first one to the second by a renaming of the alphabet symbols. We present an algorithm for searching for parameterized occurrences of a patten in a textstring when both are given in run-length encoded form. The proposed method extends to alphabets of arbitrary yet constant size with O(|rp|×|rt|) time bounds, previously achieved only with binary alphabets. Here rp and rt denote the number of runs in the corresponding encodings for p and t. For general alphabets, the time bound obtained by the present method exhibits a polynomial dependency on the alphabet size. Such a performance is better than applying convolution to the cleartext, but leaves the problem still open of designing an alphabet independent O(|rp|×|rt|) time algorithm for this problem.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 454, 5 October 2012, Pages 23-29