Streaming dictionary matching with mismatches

DOI10.1007/S00453-021-00876-XMaRDI QIDQ2118382zbMATH OpenOpenAlexFDO

Authors Tatiana Starikovskaya, Paweł Gawrychowski

Publication date 22 March 2022

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2019/10492/

zbMATH Keywords

Hamming distancepattern matchingstreaming algorithms

Mathematics Subject Classification ID

Graph theory (05Cxx) Algorithms in computer science (68Wxx)

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

• Approximate string matching using compressed suffix arrays
• Approximating LZ77 via Small-Space Multiple-Pattern Matching
• Average optimal string matching in packed strings
• Compressed Multiple Pattern Matching
• Dictionary matching and indexing with errors and don't cares
• Dictionary matching in a stream
• Dynamic dictionary matching in the online model
• Efficient randomized pattern-matching algorithms
• Efficient string matching
• Efficient string matching with k mismatches
• Exact and Approximate Pattern Matching in the Streaming Model
• Fast entropy-bounded string dictionary look-up with mismatches
• Fast index for approximate string matching
• Fast practical multi-pattern matching
• Faster algorithms for string matching with k mismatches
• Faster compressed dictionary matching
• scientific article; zbMATH DE number 177800 (Why is no real title available?)
• scientific article; zbMATH DE number 3633757 (Why is no real title available?)
• scientific article; zbMATH DE number 1263236 (Why is no real title available?)
• scientific article; zbMATH DE number 7051248 (Why is no real title available?)
• scientific article; zbMATH DE number 7651106 (Why is no real title available?)
• Improved approximate string matching using compressed suffix data structures
• Languages with mismatches
• Real-Time Streaming Multi-Pattern Search for Constant Alphabet
• Real-time streaming string-matching
• Streaming Dictionary Matching with Mismatches
• 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
• Towards unified approximate pattern matching for Hamming and \(L_1\) distance
• Worst-case efficient single and multiple string matching on packed texts in the word-RAM model

Cited in

(4)

• Dictionary matching and indexing with errors and don't cares
• Streaming Dictionary Matching with Mismatches
• Pattern masking for dictionary matching
• Regular languages in the sliding window model

Describes a project that uses

Uses Software

• Agrep

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 Q2118382)