Catalog Home Page

A prefix array for parameterized strings

Beal, R., Adjeroh, D.A. and Smyth, W.F. (2016) A prefix array for parameterized strings. Journal of Discrete Algorithms, 42 . pp. 23-34.

PDF - Authors' Version
Embargoed until January 2019.

Link to Published Version:
*Subscription may be required


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.

Publication Type: Journal Article
Murdoch Affiliation: School of Engineering and Information Technology
Publisher: Elsevier
Copyright: © 2016 Elsevier B.V.
Item Control Page Item Control Page