A black box for online approximate pattern matching

DOI10.1016/j.ic.2010.12.007zbMath1215.68279OpenAlexW2140007524MaRDI 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 approachfast approximate string matchingonline approximate matching

Mathematics Subject Classification ID

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

Related Items

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

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