Real-Time Streaming Multi-Pattern Search for Constant Alphabet

DOI10.4230/LIPIcs.ESA.2017.41zbMath1442.68280OpenAlexW2760452898MaRDI QIDQ5111729

Shay Golan, Ely Porat

Publication date: 27 May 2020

Full work available at URL: http://drops.dagstuhl.de/opus/volltexte/2017/7855/pdf/LIPIcs-ESA-2017-41.pdf/

zbMATH Keywords

fingerprintsdictionary matchingstreaming pattern matchingmulti-pattern search

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Algorithms on strings (68W32)

Related Items

Towards Optimal Approximate Streaming Pattern Matching by Matching Multiple Patterns in Multiple Streams ⋮ Streaming pattern matching with \(d\) wildcards ⋮ Streaming \(k\)-mismatch with error correcting and applications ⋮ Compressed Multiple Pattern Matching ⋮ Streaming Dictionary Matching with Mismatches ⋮ Searching Long Repeats in Streams ⋮ Streaming dictionary matching with mismatches

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Addendum to: ``Exponential time improvement for min-wise based algorithms
• Simple real-time constant-space string matching
• The space complexity of approximating the frequency moments
• Dictionary matching with a few gaps
• Deterministic Dictionaries
• Fast circular dictionary-matching algorithm
• Real-Time Streaming String-Matching
• Dictionary Matching in a Stream
• Approximating LZ77 via Small-Space Multiple-Pattern Matching
• Constructing Efficient Dictionaries in Close to Sorting Time
• Periodicity in Streams
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Efficient string matching
• The k-mismatch problem revisited
• Streaming Pattern Matching with d Wildcards
• Mind the Gap: Essentially Optimal Algorithms for Online Dictionary Matching with One Gap
• Dictionary Matching with One Gap
• An Improved Query Time for Succinct Dynamic Dictionary Matching
• Exact and Approximate Pattern Matching in the Streaming Model
• GPU-to-GPU and Host-to-Host Multipattern String Matching on a GPU
• An Efficient TCAM-Based Implementation of Multipattern Matching Using Covered State Encoding
• A Framework for Dynamic Parameterized Dictionary Matching
• Succinct Online Dictionary Matching with Improved Worst-Case Guarantees.
• Theory and practice of monotone minimal perfect hashing
• Fast moment estimation in data streams in optimal space