Gapped String Indexing in Subquadratic Space and Sublinear Query Time

Philip Bille, Inge Li Gørtz, Moshe Lewenstein +3

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…