2026-07-23T13:21:12Z https://drops.dagstuhl.de/oai

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

MONI Can Find k-MEMs Tatarnikov, Igor Shahrabi Farahani, Ardavan Kashgouli, Sana Gagie, Travis Compact data structures Burrows-Wheeler Transform run-length compression maximal exact matches Suppose we are asked to index a text T [0..n - 1] such that, given a pattern P [0..m - 1], we can quickly report the maximal substrings of P that each occur in T at least k times. We first show how we can add O (r log n) bits to Rossi et al.’s recent MONI index, where r is the number of runs in the Burrows-Wheeler Transform of T, such that it supports such queries in O (k m log n) time. We then show how, if we are given k at construction time, we can reduce the query time to O (m log n). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Igor Tatarnikov and Ardavan Shahrabi Farahani and Sana Kashgouli and Travis Gagie 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.26 urn:nbn:de:0030-drops-179802 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.26 eng https://creativecommons.org/licenses/by/4.0/legalcode