Extending the Parameterized Burrows–Wheeler Transform
Eric M. Osterkamp, Dominik Köppl · 2024
The Burrows–Wheeler transform (BWT) provides a succinct way to index text for pattern matching queries. Notable variants are (a) the extended BWT (eBWT) capable to index multiple input texts for circular pattern matching, or (b) the parameterized BWT (pBWT) for parameterized pattern matching. A natural extension is the combination of the virtues of both variants into a new data structure, whose name we coin with extended parameterized BWT (epBWT). We show that the epBWT supports circular pattern matching in context of parameterized pattern matching on multiple texts, within the same complexities as known solutions presented for the pBWT [Kim and Cho, IPL’21] for patterns shorter than the shortest indexed text.