2026-07-24T11:54:15Z https://drops.dagstuhl.de/oai

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

Repetition Aware Text Indexing for Matching Patterns with Wildcards Gibney, Daniel Huffstutler, Jackson Parthasarathi, Mano Prakash Thankachan, Sharma V. Pattern Matching Text Indexing Wildcard Matching We study the problem of indexing a text T[1..n] to support pattern matching with wildcards. The input of a query is a pattern P[1..m] containing h ∈ [0, k] wildcard (a.k.a. don't care) characters and the output is the set of occurrences of P in T (i.e., starting positions of substrings of T that matches P), where k = o(log n) is fixed at index construction. A classic solution by Cole et al. [STOC 2004] provides an index with space complexity O(n ⋅ (clog n)^k/k!)) and query time O(m+2^h log log n+occ), where c > 1 is a constant, and occ denotes the number of occurrences of P in T. We introduce a new data structure that significantly reduces space usage for highly repetitive texts while maintaining efficient query processing. Its space (in words) and query time are as follows: O(δ log (n/δ)⋅ c^k (1+(log^k (δ log n))/k!)) and O((m+2^h +occ)log n)) The parameter δ, known as substring complexity, is a recently introduced measure of repetitiveness that serves as a unifying and lower-bounding metric for several popular measures, including the number of phrases in the LZ77 factorization (denoted by z) and the number of runs in the Burrows-Wheeler Transform (denoted by r). Moreover, O(δ log (n/δ)) represents the optimal space required to encode the data in terms of n and δ, helping us see how close our space is to the minimum required. In another trade-off, we match the query time of Cole et al.’s index using O(n+δ log (n/δ) ⋅ (clogδ)^{k+ε}/k!) space, where ε > 0 is an arbitrarily small constant. We also demonstrate how these techniques can be applied to a more general indexing problem, where the query pattern includes k-gaps (a gap can be interpreted as a contiguous sequence of wildcard characters). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniel Gibney and Jackson Huffstutler and Mano Prakash Parthasarathi and Sharma V. Thankachan 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.88 urn:nbn:de:0030-drops-234656 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.88 eng https://creativecommons.org/licenses/by/4.0/legalcode