Periodicity in data streams with wildcards
From MaRDI portal
Publication:5915573
DOI10.1007/978-3-319-90530-3_9zbMath1434.68690arXiv1802.07375OpenAlexW2964104755MaRDI QIDQ5915573
Funda Ergün, Samson Zhou, Elena Grigorescu, Erfan Sadeqi Azer
Publication date: 28 November 2018
Published in: Theory of Computing Systems, Computer Science – Theory and Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1802.07375
Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27) Algorithms on strings (68W32)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Space lower bounds for online pattern matching
- Periodicity algorithms and a conjecture on overlaps in partial words
- An algorithmic toolbox for periodic partial words
- Testing periodicity
- Simple deterministic wildcard matching
- Finding repeated elements
- Time-space-optimal string matching
- String matching under a general matching relation
- Streaming \(k\)-mismatch with error correcting and applications
- Periodicity testing with sublinear samples and space
- Optimal Pattern Matching in LZW Compressed Strings
- Space-Efficient String Indexing for Wildcard Pattern Matching.
- Real-Time Streaming String-Matching
- Approximate Periodicity
- Periodicity and Cyclic Shifts via Linear Sketches
- Dictionary Matching in a Stream
- Improved Sketching of Hamming Distance with Error Correcting
- 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
- Streaming Pattern Matching with d Wildcards
- Parameterized Complexity Analysis for the Closest String with Wildcards Problem
- Exact and Approximate Pattern Matching in the Streaming Model
- The streaming k-mismatch problem
- Algorithmic Combinatorics on Partial Words
- Homomorphic fingerprints under misalignments
