A fast and simple $O(z\log n)$-space index for finding approximately longest common substrings

Nick Fagan, Jorge Hermo González, Travis Gagie

We describe how, given a text $T[\mathrm{1..}n]$ and a positive constant $\epsilon$, we can build a simple $O(z\log n)$-space index, where $z$ is the number of phrases in the LZ77 parse of $T$,…