Streaming pattern matching with \(d\) wildcards
From MaRDI portal
Publication:1741859
DOI10.1007/s00453-018-0521-7zbMath1421.68257OpenAlexW3098129897MaRDI QIDQ1741859
Tsvi Kopelowitz, Shay Golan, Ely Porat
Publication date: 7 May 2019
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-018-0521-7
Analysis of algorithms (68W40) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27) Algorithms on strings (68W32)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Simple real-time constant-space string matching
- Space lower bounds for online pattern matching
- A black box for online approximate pattern matching
- A new approach to the periodicity lemma on strings with holes
- Simple deterministic wildcard matching
- Pattern matching with don't cares and few errors
- Efficient string matching with k mismatches
- Partial words and a theorem of Fine and Wilf
- The space complexity of approximating the frequency moments
- Periodicity, morphisms, and matrices.
- A filtering algorithm for \(k\)-mismatch with don't cares
- Time-space-optimal string matching
- String matching under a general matching relation
- Approximate formulas for some functions of prime numbers
- Optimal Pattern Matching in LZW Compressed Strings
- Dictionary Matching in a Stream
- Improved Sketching of Hamming Distance with Error Correcting
- Pseudo-realtime Pattern Matching: Closing the Gap
- Verifying candidate matches in sparse and wildcard matching
- Periodicity in Streams
- Efficient randomized pattern-matching algorithms
- Fast Pattern Matching in Strings
- The k-mismatch problem revisited
- Faster algorithms for string matching with k mismatches
- Real-Time Streaming String-Matching
- Real-Time Streaming Multi-Pattern Search for Constant Alphabet
- Exact and Approximate Pattern Matching in the Streaming Model
- The streaming k-mismatch problem
- Algorithmic Combinatorics on Partial Words
- Uniqueness Theorems for Periodic Functions
- Fast moment estimation in data streams in optimal space
- Partial words and a theorem of Fine and Wilf revisited
