A simple grammar-based index for finding approximately longest common substrings

We show how, given positive constants ϵ and δ , and an α -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δ g) time finds w.h.p. a substring of P that occurs in T and whose length is at least a ( 1 - ϵ ) fraction of the longest common substring of P and T . The correctness can be ensured within the same expected query time.