scientific article; zbMATH DE number 7375847

DOI10.4230/LIPIcs.APPROX-RANDOM.2017.42zbMath1467.68237arXiv1708.04381MaRDI QIDQ5002646

Funda Ergün, Elena Grigorescu, Azer Erfan Sadeqi, Samson Zhou

Publication date: 28 July 2021

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

pattern matchingrandomized algorithmsstring algorithmsstreaming algorithmssublinear algorithms

Mathematics Subject Classification ID

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

Related Items

Periodicity in data streams with wildcards, Quasi-Periodicity in Streams

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Space lower bounds for online pattern matching
• Testing periodicity
• Time-space-optimal string matching
• Streaming \(k\)-mismatch with error correcting and applications
• Periodicity testing with sublinear samples and space
• Optimal Pattern Matching in LZW Compressed Strings
• Approximate Periodicity
• Periodicity and Cyclic Shifts via Linear Sketches
• Dictionary Matching in a Stream
• Improved Sketching of Hamming Distance with Error Correcting
• Periodicity in Streams
• Efficient randomized pattern-matching algorithms
• Fast Pattern Matching in Strings
• The k-mismatch problem revisited
• Streaming Pattern Matching with d Wildcards
• Exact and Approximate Pattern Matching in the Streaming Model
• Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams.
• Homomorphic fingerprints under misalignments