2026-07-22T12:55:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23114 2025-10-02T12:37:56Z ddc:004 open_access

Text Indexing for Simple Regular Expressions Bannai, Hideo Bille, Philip Gørtz, Inge Li Landau, Gad M. Navarro, Gonzalo Prezza, Nicola Steiner, Teresa Anna Tarnow, Simon Rumle Text indexing regular expressions data structures We study the problem of indexing a text T[1..n] ∈ Σⁿ so that, later, given a query regular expression pattern R of size m = |R|, we can report all the occ substrings T[i..j] of T matching R. The problem is known to be hard for arbitrary patterns R, so in this paper, we consider the following two types of patterns. (1) Character-class Kleene-star patterns of the form P₁ D^* P₂, where P₁ and P₂ are strings and D = {c₁, …, c_k} ⊂ Σ is a character-class (shorthand for the regular expression (c₁ | c₂ | ⋯ | c_k)) and (2) String Kleene-star patterns of the form P₁ P^* P₂ where P, P₁ and P₂ are strings. In case (1), we describe an index of O(nlog^{1+ε}n) space (for any constant ε > 0) solving queries in time O(m + log n/log log n + occ) on constant-sized alphabets. We also describe a general solution for any alphabet size. This result is conditioned on the existence of an anchor: a character of P₁P₂ that does not belong to D. We justify this assumption by proving that no efficient indexing solution can exist if an anchor is not present unless the Set Disjointness Conjecture fails. In case (2), we describe an index of size O(n) answering queries in time O(m + (occ+1)log^{ε}n) on any alphabet size. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hideo Bannai and Philip Bille and Inge Li Gørtz and Gad M. Landau and Gonzalo Navarro and Nicola Prezza and Teresa Anna Steiner and Simon Rumle Tarnow 2025 Is Part Of LIPIcs, Volume 331, 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2025.20 urn:nbn:de:0030-drops-231143 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2025.20 eng https://creativecommons.org/licenses/by/4.0/legalcode