Abstract

We show how, given positive constants $$\epsilon $$ and $$\delta $$, and an $$\alpha $$ -balanced straight-line program with g rules for a text T[1.n], we can build an O(g)-space index that, given a pattern P[1.m], in $$O(m\log ^\delta g)$$ time finds w.h.p. a substring of P that occurs in T and whose length is at least a $$(1 - \epsilon )$$ fraction of the longest common substring of P and T. The correctness can be ensured within the same expected query time.