Journal article
A prefix array for parameterized strings
Journal of Discrete Algorithms, Vol.42, pp.23-34
2016
Abstract
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.
Details
- Title
- A prefix array for parameterized strings
- Authors/Creators
- R. Beal (Author/Creator) - West Virginia UniversityD.A. Adjeroh (Author/Creator) - West Virginia UniversityW.F. Smyth (Author/Creator) - McMaster University
- Publication Details
- Journal of Discrete Algorithms, Vol.42, pp.23-34
- Publisher
- Elsevier
- Identifiers
- 991005542690207891
- Copyright
- © 2016 Elsevier B.V.
- Murdoch Affiliation
- School of Engineering and Information Technology
- Language
- English
- Resource Type
- Journal article
Metrics
331 File views/ downloads
38 Record Views