کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4951324 1441210 2017 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A prefix array for parameterized strings
ترجمه فارسی عنوان
آرایه پیشوند برای رشته های پارامتریک
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

A parameterized string (p-string) is a generalization of the traditional string over two alphabets: a constant alphabet and a parameter alphabet. A parameterized match (p-match) exists between two p-strings if the constants match exactly and if there exists a bijection between the parameter symbols. Historically, p-strings have been leveraged for source code cloning, plagiarism detection, and biological sequence structural similarity. In this work, we identify the connection between the p-match and music, one of several applications to motivate our study of holes in p-strings, and prefix array-based data structures for p-strings. First, we introduce the parameterized prefix array (pPA) for p-strings and its succinct representation, the compact parameterized prefix array (cpPA). We show an interesting construction of the cpPA via the parameterized longest previous factor (pLPF), a more recently proposed array with connections to various pattern matching data structures and LZ factorization. Next, we introduce the parameterized string with holes (hp-string), needed to address a special form of indeterminate pattern matching with p-strings. Then, we show how to construct the compact prefix array for hp-strings. Finally, we discuss applications for our data structures.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 42, January 2017, Pages 23-34
نویسندگان
, , ,