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

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