2026-08-06T10:27:53Z https://drops.dagstuhl.de/oai

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

Compressed Indexing for Consecutive Occurrences Gawrychowski, Paweł Gourdel, Garance Starikovskaya, Tatiana Steiner, Teresa Anna Compressed indexing two patterns consecutive occurrences The fundamental question considered in algorithms on strings is that of indexing, that is, preprocessing a given string for specific queries. By now we have a number of efficient solutions for this problem when the queries ask for an exact occurrence of a given pattern P. However, practical applications motivate the necessity of considering more complex queries, for example concerning near occurrences of two patterns. Recently, Bille et al. [CPM 2021] introduced a variant of such queries, called gapped consecutive occurrences, in which a query consists of two patterns P₁ and P₂ and a range [a,b], and one must find all consecutive occurrences (q₁,q₂) of P₁ and P₂ such that q₂-q₁ ∈ [a,b]. By their results, we cannot hope for a very efficient indexing structure for such queries, even if a = 0 is fixed (although at the same time they provided a non-trivial upper bound). Motivated by this, we focus on a text given as a straight-line program (SLP) and design an index taking space polynomial in the size of the grammar that answers such queries in time optimal up to polylog factors. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Paweł Gawrychowski and Garance Gourdel and Tatiana Starikovskaya and Teresa Anna Steiner 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.12 urn:nbn:de:0030-drops-179666 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.12 eng https://creativecommons.org/licenses/by/4.0/legalcode