A black box for online approximate pattern matching

DOI10.1016/j.ic.2010.12.007zbMath1215.68279MaRDI QIDQ716330

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

Publication date: 28 April 2011

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2010.12.007

zbMATH Keywords

black box approach; fast approximate string matching; online approximate matching

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68W27: Online algorithms; streaming algorithms

68W32: Algorithms on strings

Related Items

Unnamed Item, On-line weighted pattern matching, Streaming pattern matching with \(d\) wildcards, Streaming \(k\)-mismatch with error correcting and applications, Upper and Lower Bounds for Dynamic Data Structures on Strings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Simple deterministic wildcard matching
• Efficient string matching with k mismatches
• Fast algorithms for approximately counting mismatches
• Approximate string matching for music analysis
• Efficient 2-dimensional approximate matching of half-rectangular figures
• k-Mismatch with Don’t Cares
• Verifying candidate matches in sparse and wildcard matching
• Generalized String Matching
• Faster image template matching in the sum of the absolute value of differences measure
• Faster algorithms for string matching with k mismatches
• Combinatorial Pattern Matching
• Combinatorial Pattern Matching
• Fast on-line integer multiplication