Streaming Dictionary Matching with Mismatches

DOI10.4230/LIPICS.CPM.2019.21MaRDI QIDQ5088912zbMATH OpenOpenAlexFDO

Authors Paweł Gawrychowski, Tatiana Starikovskaya

Publication date 18 July 2022

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

zbMATH Keywords

Hamming distancemultiple pattern matchingstreaming

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• Streaming dictionary matching with mismatches
• The streaming \(k\)-mismatch problem
• The \(k\)-mismatch problem revisited
• Streaming \(k\)-mismatch with error correcting and applications
• Towards optimal approximate streaming pattern matching by matching multiple patterns in multiple streams

Cites work

• Approximating LZ77 via Small-Space Multiple-Pattern Matching
• Average optimal string matching in packed strings
• Dictionary matching and indexing with errors and don't cares
• Dictionary matching in a stream
• Efficient randomized pattern-matching algorithms
• Efficient string matching
• Exact and Approximate Pattern Matching in the Streaming Model
• Fast practical multi-pattern matching
• Fast prefix search in little space, with applications
• Faster compressed dictionary matching
• scientific article; zbMATH DE number 3633757 (Why is no real title available?)
• scientific article; zbMATH DE number 7051248 (Why is no real title available?)
• Multiple approximate string matching
• On randomized one-round communication complexity
• Real-Time Streaming Multi-Pattern Search for Constant Alphabet
• Real-time streaming string-matching
• Succinct Dictionary Matching with No Slowdown
• Succinct online dictionary matching with improved worst-case guarantees
• The \(k\)-mismatch problem revisited
• The streaming \(k\)-mismatch problem
• Towards optimal approximate streaming pattern matching by matching multiple patterns in multiple streams
• Worst case efficient single and multiple string matching in the RAM model

Cited in

(7)

• Streaming dictionary matching with mismatches
• Dictionary matching and indexing with errors and don't cares
• Pattern masking for dictionary matching
• Sorting circular suffixes in linear time
• Substring complexity in sublinear space
• Improved circular dictionary matching
• Sorting circular suffixes in linear time

This page was built for publication: Streaming Dictionary Matching with Mismatches

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5088912)