# Text Indexing for Faster Gapped Pattern Matching
## 1 Introduction  
Let \(T[1\ldots n]\) be a string (called the text) over a polynomially sized alphabet and \(P=P_{1}[\alpha\ldots\beta]P_{2}\) be a _gapped pattern_, where \(P_{1}\) and \(P_{2}\) are strings and \([\alpha\ldots\beta]\) is an integer interval called the _gap range_. An occurrence of \(P\) in \(T\) is represented as a pair \((i,j)\) such that \(T[i\ldots i+|P_{1}|)=P_{1}\), \(T[j\ldots j+|P_{2}|)=P_{2}\) with gap \(j-(i+|P_{1}|)\in[\alpha\ldots\beta]\). Locating occurrences of gapped patterns has numerous applications in computational biology [1; 2; 3; 4; 5; 6; 7] and text mining [8; 9; 10; 11]. The algorithmic variant of the gapped pattern matching problem is well studied [12; 13] and can be solved in \(\widetilde{\mathcal{O}}(n+m+\mathrm{occ})\) time (\(\widetilde{\mathcal{O}}(\cdot)\) suppresses polylogarithmic factors, in particular, \((\log n)^{k}=\widetilde{\mathcal{O}}(1)\) for any constant \(k\).) [3; 6; 14; 15; 16].  
This work focuses on an indexing version of the problem where the text \(T\) is known during preprocessing. The gapped pattern \(P=P_{1}[\alpha\ldots\beta]P_{2}\) is provided as a query. Formally, we consider Problem 1.  
**Problem 1** (Gapped String Indexing).: _Preprocess: A text \(T[1\ldots n]\). Query: Given a gapped pattern \(P=P_{1}[\alpha\ldots\beta]P_{2}\), report all occurrences of \(P\) in \(T\)._  
In recent work, [PERSON] et al. [17] showed that for all \(0\leq\delta\leq 1\), an index for Problem 1 can be constructed occupying \(\widetilde{\mathcal{O}}(n^{2-\delta/3})\) or \(\widetilde{\mathcal{O}}(n^{3-2\delta})\) space, and answering queries \(\widetilde{\mathcal{O}}(|P_{1}|+|P_{2}|+n^{\delta}\cdot(\mathrm{occ}+1))\) time. Our main result is an index that requires similar space but achieves query times parameterized by the gaps present in the occurrences. This is stated formally in Theorem 1 below. In particular, our result improves the case where gaps for most occurrences are small.  
**Theorem 1**.: _For all \(0\leq\delta\leq 1\), there exists an index for Gapped String Indexing that occupies \(\widetilde{\mathcal{O}}(n^{2-\delta/3})\) space and answers queries in time_  
\[\widetilde{\mathcal{O}}(|P_{1}|+|P_{2}|+n^{\delta}\cdot(1+\mathrm{occ}^{1- \delta})+\sum_{g\in[\alpha\cdot\beta]}\mathrm{occ}_{g}\cdot g^{\delta})\]  
_where \(\mathrm{occ}_{g}\) is the number of occurrences with gap \(g\)._  
Our main technique revolves around solving the following bounded variant of Gapped String Indexing, which may be of independent interest.  
**Problem 2** (Bounded Gapped String Indexing).: _Preprocess: A text \(T[1\ldots n]\) and integer \(G\). Query: Given a gapped pattern \(P=P_{1}[\alpha\ldots\beta]P_{2}\) where \(\beta<G\), report all occurrences of \(P\) in \(T\)._  
For Problem 2, we provide a solution with space and query complexity stated in Theorem 2.  
**Theorem 2**.: _For every \(0\leq\delta\leq 1\), there exists an index for Bounded Gapped String Indexing that occupies \(\widetilde{\mathcal{O}}(n^{2-\delta/3})\) space and answers queries in time_  
\[\widetilde{\mathcal{O}}(|P_{1}|+|P_{2}|+n^{\delta}\cdot(1+\mathrm{occ}^{1- \delta})+G^{\delta}\cdot\mathrm{occ})\]  
_where \(\mathrm{occ}\) is the size of the output._  
To prove Theorem 2, we build on previous results for the Gapped Set Intersection Problem (defined formally in Section 2), developing techniques for the bounded-gap case. We utilize a blocking technique based on binary trees, which when combined with a generalized form of the Kraft-McMillan inequality, allows us to achieve an improved query time (Lemma 9). Our preprocessing techniques differ from those of [PERSON] et al. [17] in that we rely on the bounded nature of the gaps to perform the proposed blocking technique. Indeed, Theorem 2 is accomplished through extra preprocessing (blocking and building data structures for blocks) that is possible only when an upper bound \(G>\beta\) is known in advance. As described in Section 3.6, Theorem 1 is then achieved by applying Theorem 2 for different ranges of \(G\).