A Black Box for Online Approximate Pattern Matching

DOI10.1007/978-3-540-69068-9_15MaRDI QIDQ3506949zbMATH OpenOpenAlexFDO

Authors Raphaël Clifford, Klim Efremenko, Benny Porat, Ely Porat

Publication date 17 June 2008

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-69068-9_15

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Recommendations

• A black box for online approximate pattern matching
• Pattern matching in pseudo real-time
• Space Lower Bounds for Online Pattern Matching
• Space lower bounds for online pattern matching
• The \(k\)-mismatch problem revisited

Cites work

• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 3471577 (Why is no real title available?)
• scientific article; zbMATH DE number 2119723 (Why is no real title available?)
• scientific article; zbMATH DE number 1424324 (Why is no real title available?)
• Approximate string matching for music analysis
• Combinatorial Pattern Matching
• Combinatorial Pattern Matching
• Communication complexity of sum-type functions invariant under translation
• Data streams: algorithms and applications.
• Efficient 2-dimensional approximate matching of half-rectangular figures
• Efficient string matching with k mismatches
• Faster algorithms for string matching with k mismatches
• Faster image template matching in the sum of the absolute value of differences measure
• Generalized String Matching
• Simple deterministic wildcard matching
• Verifying candidate matches in sparse and wildcard matching
• k-Mismatch with Don’t Cares

Cited in

(5)

• Pattern matching in pseudo real-time
• A black box for online approximate pattern matching
• On pattern matching with \(k\) mismatches and few don't cares
• Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model
• On string matching with mismatches

This page was built for publication: A Black Box for Online Approximate Pattern Matching

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