2022/10/18 by Navarro, Gonzalo
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2210.09914
We consider the problem of computing the Maximal Exact Matches (MEMs) of a given pattern P[1 .. m] on a large repetitive text collection T[1 .. n], which is represented as a (hopefully much smaller) run-length context-free grammar of size grl. We show that the problem can be solved in time O(m2 logεn), for any constant ε> 0, on a data structure of size O(grl). Further, on a locally consistent grammar of size O(δlog\fracnδ), the time decreases to O(mlog m(log m + logεn)). The value δ is a function of the substring complexity of T and Ω(δlog\fracnδ) is a tight lower bound on the compressibility of repetitive texts T, so our structure has optimal size in terms of n and δ. We extend our results to several related problems, such as finding k-MEMs, MUMs, rare MEMs, and applications.