Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

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
Download (544kB) | Preview
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.

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


Downloads per month over past year