  In Gapped String Indexing, the goal is to compactly represent a string $S$ of
length $n$ such that for any query consisting of two strings $P_1$ and $P_2$,
called patterns, and an integer interval $[\alpha, \beta]$, called gap range,
we can quickly find occurrences of $P_1$ and $P_2$ in $S$ with distance in
$[\alpha, \beta]$. Gapped String Indexing is a central problem in computational
biology and text mining and has thus received significant research interest,
including parameterized and heuristic approaches. Despite this interest, the
best-known time-space trade-offs for Gapped String Indexing are the
straightforward $O(n)$ space and $O(n+occ)$ query time or $\Omega(n^2)$ space
and $\tilde{O}(|P_1| + |P_2| + occ)$ query time.
  We break through this barrier obtaining the first interesting trade-offs with
polynomially subquadratic space and polynomially sublinear query time. In
particular, we show that, for every $0\leq \delta \leq 1$, there is a data
structure for Gapped String Indexing with either $\tilde{O}(n^{2-\delta/3})$ or
$\tilde{O}(n^{3-2\delta})$ space and $\tilde{O}(|P_1| + |P_2| + n^{\delta}\cdot
(occ+1))$ query time, where $occ$ is the number of reported occurrences.
  As a new tool towards obtaining our main result, we introduce the Shifted Set
Intersection problem. We show that this problem is equivalent to the indexing
variant of 3SUM (3SUM Indexing). Via a series of reductions, we obtain a
solution to the Gapped String Indexing problem. Furthermore, we enhance our
data structure for deciding Shifted Set Intersection, so that we can support
the reporting variant of the problem. Via the obtained equivalence to 3SUM
Indexing, we thus give new improved data structures for the reporting variant
of 3SUM Indexing, and we show how this improves upon the state-of-the-art
solution for Jumbled Indexing for any alphabet of constant size $\sigma>5$.
