2026-07-24T02:02:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17978 2024-03-06T11:00:46Z ddc:004 open_access

Computing MEMs on Repetitive Text Collections Navarro, Gonzalo grammar-based indices maximal exact matches locally consistent grammars substring complexity 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 g_{rl}. We show that the problem can be solved in time O(m² log^ε n), for any constant ε > 0, on a data structure of size O(g_{rl}). Further, on a locally consistent grammar of size O(δ log n/δ), the time decreases to O(m log m(log m + log^ε n)). The value δ is a function of the substring complexity of T and Ω(δ log n/δ) is a tight lower bound on the compressibility of repetitive texts T, so our structure has optimal size in terms of n and δ. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gonzalo Navarro 2023 Is Part Of LIPIcs, Volume 259, 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2023.24 urn:nbn:de:0030-drops-179787 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.24 eng https://creativecommons.org/licenses/by/4.0/legalcode