# Text Indexing for Faster Gapped Pattern Matching
## 2 A Preliminary Solution  
Before introducing our main solution, we first present a preliminary approach. While this solution does not achieve the query efficiency required to prove Theorem 1, it serves as a valuable foundation for our solution. As an initial step, we introduce the following two problem formulations from [17]. **Problem 3** (Gapped Set Intersection (with Reporting)). : _Preprocess: A collection of subsets \(S_{1}\),..., \(S_{k}\) of total size \(N=\sum_{i=1}^{k}|S_{i}|\) over integer universe \([0\dots U]\). Query: Given \((i,j,\alpha,\beta)\), report if there exists (report all, resp.) \((a,b)\in S_{i}\times S_{j}\) where there exists \(s\in[\alpha\dots\beta]\) such that \(a+s=b\)._  
We also define the bounded version of Problem 3, analogous to Problem 2. Specifically, the bounded problem formulation provides a collection of subsets \(S_{1}\),..., \(S_{k}\), and an integer \(G\) for preprocessing. A query consists of the tuple \((i,j,\alpha,\beta)\) with the additional guarantee that \(\beta<G\). We will utilize the following results from [PERSON] et al. [17]. **Lemma 1** (Index for Gapped Set Intersection (Theorems 5 and 6 from [17])). : _For every \(0\leq\delta\leq 1\), there is a data structure for the Gapped Set Intersection that occupies \(\widetilde{\mathcal{O}}(N^{2-\delta/3})\) space and answers existential queries in time \(\widetilde{\mathcal{O}}(N^{\delta})\) and reporting queries in time \(\widetilde{\mathcal{O}}(N^{\delta}\cdot(\operatorname{occ}+1))\), where \(\operatorname{occ}\) is the size of the output._  
Lemma 2 allows us to focus on Problem 3 for the majority of the remaining work. **Lemma 2** (Reduction to Bounded Gapped Set Intersection (Adapted from [17])). : _Assume there is a data structure for the Bounded Gapped Set Intersection (with Reporting) using \(s(N)\) space that answers existential queries in time \(t(N)\) and reporting queries in time \(t(N)\cdot(1+\operatorname{occ})\). Then, there exists a data structure for Bounded Gapped String Indexing using \(\widetilde{\mathcal{O}}(n+s(n))\) space. It can answer existential queries in time \(\widetilde{\mathcal{O}}(|P_{1}|+|P_{2}|+t(n))\) and reporting queries in time \(\widetilde{\mathcal{O}}(|P_{1}|+|P_{2}|+t(n)\cdot(1+\text{occ}))\), where \(n\) is the length of the input text and \(\text{occ}\) is the size of the output._  
For completeness, we sketch an adaptation of the proof from [17]. Proof. : We begin with the array \(S_{2}[1\ldots n]\) such that \(S_{2}[i]=\text{SA}[i]\), where \(\text{SA}[\cdot]\) is the suffix array of \(T\). We also define the array \(S_{1}[1\ldots n]\), where \(S_{1}[i]=n-\text{SA}[i]^{R}+1\), and \(\text{SA}[\cdot]^{R}\) is the suffix array of the reverse string \(T^{R}\). Both arrays are decomposed into subsets corresponding to dyadic intervals of the form \([1+\kappa\cdot 2\ldots(\kappa+1)\cdot 2^{l}]\), where \(0\leq\kappa\leq\lfloor n/2^{l}\rfloor-1\) and \(0\leq j\leq\lfloor\log n\rfloor\). These subsets serve as the input to the Gapped Set Intersection instance. Notably, the sum of the subset cardinalities is \(\mathcal{O}(n\log n)\). Given a query \(P_{1}[\alpha\ldots\beta]P_{2}\), we decompose the suffix range for \(P_{1}^{R}\) into a collection of \(\mathcal{O}(\log n)\) dyadic-sized subarrays of \(S_{1}\), corresponding to precomputed subsets. We denote this collection by \(\mathcal{A}\). Similarly, we decompose the suffix range of \(P_{2}\) into a collection of \(\mathcal{O}(\log n)\) dyadic intervals corresponding to precomputed subsets of \(S_{2}\) denoted by \(\mathcal{B}\). We then perform \(\mathcal{O}(\log^{2}n)\) queries (For notational brevity here, we abuse notation slightly. The actual query would be on the indices corresponding to subsets \(A\) and \(B\).) \((A,B,\alpha,\beta)\) for all \(A\in\mathcal{A}\) and \(B\in\mathcal{B}\). It is important to note that the bounds \(\alpha\) and \(\beta\) remain unchanged throughout the reduction.