# Text Indexing for Faster Gapped Pattern Matching
## 3 An Improved Solution
### Query Time Analysis
The combined time used for \"contains_occurrence\" calls is polylogarithmic factors from  
\[\sum_{v\in\mathcal{V}}\left(\frac{N}{2^{h(u)}}\right)^{\delta}=N^{\delta}\sum _{v\in\mathcal{V}}\left(\frac{1}{2^{h(v)}}\right)^{\delta}. \tag{1}\]  
We next apply [PERSON]'s inequality to obtain the bound  
\[\sum_{v\in\mathcal{V}}\left(\frac{1}{2^{h(v)}}\right)^{\delta}=\sum_{v\in \mathcal{V}}\left(\frac{1}{2^{h(v)}}\right)^{\delta}1^{1-\delta}\leq\  
Substituting into Equation (1), we obtain that the time used for \"contains_occurrence\" calls is \(\widetilde{\mathcal{O}}(N^{\delta}(1+s)^{1-\delta})\).  
Next, we consider the time used by calls to \"report_all_occurrences\". By Lemma 1, each leaf \(v\) on which \"report_all_occurrences\" is called takes time \(\widetilde{\mathcal{O}}(G^{\delta}(1+\mathrm{occ}_{v}))\), where \(\mathrm{occ}_{v}\) denotes the number of occurrences contained in the subarray for node \(v\). To bound the time complexity, we should bound the number of times an occurrence can be reported over all blocks. To this end, we prove Lemma 8.  
Lemma 8: _Every subarray \(A^{\prime}=A[a\,..\,b]\) of size \(b-a+1\leq G\) has a non-empty intersection with \(\mathcal{O}(1)\) leaf's subarrays._  
Proof.: Consider first the tree structure without any middle child leaves. In this case, the leaves are all disjoint and, by Lemma 4, have subarray size at least \(G\). Hence, at most two non-middle children leaves have non-empty intersections with \(A^{\prime}\).  
Now, we incorporate the middle children. We consider the middle children leaves as being ordered according to their midpoint.  
_Claim: The difference between consecutive midpoints of middle children leaves is at least \(G\)._ To see this, consider a middle child of \(u\) with midpoint \(m_{u}=\lfloor(l_{u}+r_{u})/2\rfloor\) and a middle child of \(v\) with midpoint \(m_{v}=\lfloor(l_{v}+r_{v})/2\rfloor\) immediately preceding \(m_{u}\) in the order. If \(v\) is in the left subtree of \(u\), since  
\[m_{v}+G<\frac{l_{v}+r_{v}}{2}+\frac{r_{v}-l_{v}+1}{2}=r_{v}+\frac{1}{2},\]  
we have \(m_{v}+G\leq r_{v}\leq m_{u}\), where the last inequality follows from Line 6 in Algorithm 1. Hence, \(m_{u}-m_{v}\geq G\). If, on the other hand, \(v\) is not in the left subtree of \(u\), then since the middle child of \(v\) is ordered before the middle child of \(u\), \(v\) cannot be in the right subtree of \(u\). If \(v\) is the parent of \(u\), then by a similar argument,  
\[\sum_{v\in V}2^{-h(v)} =2^{0}+\sum_{v\in V_{L}}2^{-(h_{L}(v)+1)}+\sum_{v\in V_{R}}2^{-(h_ {R}(v)+1)}\]0  
and we have \(m_{u}-G+1\geq l_{u}\geq m_{v}+1\), where the last inequality follows from Line 7 in Algorithm 1. Hence, \(m_{u}-m_{v}\geq G\). In any other remaining cases, \(u\) and \(v\) must share either some lowest common ancestor or an intermediate vertex on the path from \(v\) to \(u\). Call this vertex \(w\). Observe that the middle child of \(w\) sits in the ordering between the middle children of \(u\) and \(v\), a contradiction that makes the last remaining cases impossible. Applying the above claim, we first observe that the range of possible midpoints of middle children leaves that can have a non-empty intersection with \(A^{\prime}\) is \([a-G\,..\,b+G-1]\). Therefore, an upper bound on the number of middle children leaves that can have a non-empty intersection with \(A^{\prime}\) is given by  
\[\sum_{v\in V}2^{-h(v)} =2^{0}+\sum_{v\in V_{L}}2^{-(h_{L}(v)+1)}+\sum_{v\in V_{R}}2^{-(h_ {R}(v)+1)}\]1  
Hence, at most three middle children leaves have intersections with \(A^{\prime}\). Combined with at most two non-middle children leaves intersecting \(A^{\prime}\), we arrive at the desired result. As a result of Lemma 8, each occurrence is reported at most \(\mathcal{O}(1)\) times, and the removal of potential duplicates does not affect the total asymptotic time complexity. Over all \"report_all_occurrences\" calls, the time is \(\widetilde{\mathcal{O}}(G^{\delta}(s+\mathrm{occ}))\).