Dictionary Matching in a Stream

DOI10.1007/978-3-662-48350-3_31zbMath1443.68218arXiv1504.06242OpenAlexW1832313123MaRDI QIDQ3452800

Tatiana Starikovskaya, Ely Porat, Benjamin Sach, Raphaël Clifford, Allyx Fontaine

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1504.06242

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27) Algorithms on strings (68W32)

Related Items (15)

Approximating LZ77 via Small-Space Multiple-Pattern Matching ⋮ Unnamed Item ⋮ Space-time trade-offs for finding shortest unique substrings and maximal unique matches ⋮ Unnamed Item ⋮ Towards Optimal Approximate Streaming Pattern Matching by Matching Multiple Patterns in Multiple Streams ⋮ Streaming pattern matching with \(d\) wildcards ⋮ Periodicity in data streams with wildcards ⋮ Unnamed Item ⋮ Streaming \(k\)-mismatch with error correcting and applications ⋮ Compressed Multiple Pattern Matching ⋮ Streaming Dictionary Matching with Mismatches ⋮ Searching Long Repeats in Streams ⋮ Tight tradeoffs for real-time approximation of longest palindromes in streams ⋮ Real-Time Streaming Multi-Pattern Search for Constant Alphabet ⋮ Streaming dictionary matching with mismatches

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pattern matching in pseudo real-time
• Pattern Matching in Multiple Streams
• Real-Time Streaming String-Matching
• Simple Real-Time Constant-Space String Matching
• Periodicity and Cyclic Shifts via Linear Sketches
• Constructing Efficient Dictionaries in Close to Sorting Time
• Pseudo-realtime Pattern Matching: Closing the Gap
• Efficient randomized pattern-matching algorithms
• Efficient string matching
• Fast Pattern Matching in Strings
• Two-way string-matching
• Network Applications of Bloom Filters: A Survey
• Exact and Approximate Pattern Matching in the Streaming Model

This page was built for publication: Dictionary Matching in a Stream