2026-07-20T05:47:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7326 2024-03-06T10:40:05Z ddc:004 open_access

Document Listing on Repetitive Collections with Guaranteed Performance Navarro, Gonzalo repetitive string collections document listing grammar compression range minimum queries succinct data structures We consider document listing on string collections, that is, finding in which strings a given pattern appears. In particular, we focus on repetitive collections: a collection of size N over alphabet [1,a] is composed of D copies of a string of size n, and s single-character edits are applied on the copies. We introduce the first document listing index with size O~(n + s), precisely O((n lg a + s lg^2 N) lg D) bits, and with useful worst-case time guarantees: Given a pattern of length m, the index reports the ndoc strings where it appears in time O(m^2 + m lg N (lg D + lg^e N) ndoc), for any constant e > 0. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gonzalo Navarro 2017 Is Part Of LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2017.4 urn:nbn:de:0030-drops-73268 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2017.4 eng https://creativecommons.org/licenses/by/3.0/legalcode