Color Distance Oracles and Snippets: Separation Between Exact and Approximate Solutions

Noam Horowicz, Tsvi Kopelowitz

In the snippets problem, the goal is to preprocess text $T$ so that given two patterns $P_1$ and $P_2$, one can locate the occurrences of the two patterns in $T$ that are closest t…