Bounded-Ratio Gapped String Indexing

In the gapped string indexing problem, one is given a text T[1..n] to preprocess. At query time, a gapped pattern P=P[α..β]P and an integer range [α..β] are provided, where P and P are strings of total length m. The goal of the query is to report all pairs of occurrences of P and P with a gap falling within [α..β]. An existing (conditional) lower bound reveals that any index with query time O~(m+occ) must occupy almost quadratic space, where occ is the output size. However, there are interesting special cases where more efficient solutions are possible. For example, queries with a bounded gap, i.e., β≤G (fixed at construction) can be answered optimally using an O~(nG) space structure. In this paper, we bring out an interesting version of the problem where rather than having a fixed upper bound on β, we fix γ and allow any β≤γ·m (i.e., allow longer gaps for longer patterns; gap-to-pattern ratio is bounded). We show that such queries can be answered optimally using an O~(nγ) space structure.