Search

The Parikh vector p(s) of a string s over a finite ordered alphabet Σ = {a1, ..., aσ} is defined as the vector of multiplicities of the characters, p(s) = (p1, ..., pσ), where pi = |{j | sj = ai}|. Parikh vector q occurs in s if s has a substring t with p(t) = q. The problem of searching for a query q in a text s of length n can be solved simply and worst-case optimally with a sliding window approach in O(n) time. We present two novel algorithms for the case where the text is fixed and many queries arrive over time. The first algorithm only decides whether a given Parikh vector appears in a binary text. It uses a linear size data structure and decides each query in O(1) time. The preprocessing can be done trivially in Θ(n2) time. The second algorithm finds all occurrences of a given Parikh vector in a text over an arbitrary alphabet of size σ ≥ 2 and has sub-linear expected time complexity. More precisely, we present two variants of the algorithm, both using an O(n) size data structure, each of which can be constructed in O(n) time. The first solution is very simple and easy to implement and leads to an expected query time of $O(n{(\frac{\sigma }{{\log \,\sigma }})^{1/2}}\frac{{\log \,m}}{{\sqrt m }})$, where m = ∑i qi is the length of a string with Parikh vector q. The second uses wavelet trees and improves the expected runtime to $O(n{(\frac{\sigma }{{\log \,\sigma }})^{1/2}}\frac{1}{{\sqrt m }})$, i.e., by a factor of log m. [ABSTRACT FROM AUTHOR]

The extended Burrows-Wheeler Transform (eBWT) [Mantaci et al. TCS 2007] is a variant of the BWT, introduced for collections of strings. In this paper, we present the extended r-index , an analogous data structure to the r -index [Gagie et al. JACM 2020]. It occupies O (r) words, with r the number of runs of the eBWT, and offers the same functionalities as the r -index. We also show how to efficiently support finding maximal exact matches (MEMs). We implemented the extended r -index and tested it on circular bacterial genomes and plasmids, comparing it to five state-of-the-art compressed text indexes. While our data structure maintains similar time and memory requirements for answering pattern matching queries as the original r -index, it is the only index in the literature that can naturally be used for both circular and linear input collections. This is an extended version of [Boucher et al., r-indexing the eBWT, SPIRE 2021]. • Introducing the extended r -index (r -index for the eBWT). • Full cyclic pattern matching functionality in O (r) space. • Efficient construction of the extended r -index. • Computation of MEMs with the extended r -index. • Experimental comparison with several compressed indexes on real biological data. [ABSTRACT FROM AUTHOR]