###
A Simple Grammar-based Index for Finding Approximately Longest Common Substrings

####
Travis Gagie, Sana Kashgouli, and Gonzalo Navarro

We show how, given positive constants *e* and *d*, and an
*a*-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^d g)* time finds with high probability a
substring of *P* that occurs in *T* and whose length is at least a
*(1-e)* fraction of the longest common substring of *P* and *T*.