2014/01/03 by Moshe Lewenstein, Yakov Nekrich, Lewenstein, Moshe +3 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Network Packet Processing and Optimization
paper · pdf · doi:10.48550/arxiv.1401.0625
openalex publication_date 2014/01/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we describe compressed indexes that support pattern matching queries for strings with wildcards. For a constant size alphabet our data structure uses O(nlogεn) bits for any ε>0 and reports all occ occurrences of a wildcard string in O(m+σg ⋅μ(n) + occ) time, where μ(n)=o(logloglog n), σ is the alphabet size, m is the number of alphabet symbols and g is the number of wildcard symbols in the query string. We also present an O(n)-bit index with O((m+σg+occ)logεn) query time and an O(n(loglog n)2)-bit index with O((m+σg+occ)loglog n) query time. These are the first non-trivial data structures for this problem that need o(nlog n) bits of space.