Towards Unified Approximate Pattern Matching for Hamming and L_1 Distance

DOI10.4230/LIPIcs.ICALP.2018.62zbMath1499.68423OpenAlexW2885786319MaRDI QIDQ5002739

Paweł Gawrychowski, Przemysław Uznański

Publication date: 28 July 2021

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9066/pdf/LIPIcs-ICALP-2018-62.pdf/

zbMATH Keywords

Hamming distanceapproximate pattern matching\(L_1\) distanceconditional lower bounds

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Approximation algorithms (68W25) Algorithms on strings (68W32)

Related Items (10)

Elastic-degenerate string matching with 1 error ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Circular pattern matching with \(k\) mismatches ⋮ Hamming Distance Completeness ⋮ Approximating Approximate Pattern Matching ⋮ Elastic-Degenerate String Matching via Fast Matrix Multiplication ⋮ Recent advances in text-to-pattern distance algorithms ⋮ Streaming dictionary matching with mismatches

Cites Work

• Unnamed Item
• Unnamed Item
• Approximate pattern matching with the \(L_1\), \(L_2\) and \(L_\infty\) metrics
• Efficient string matching with k mismatches
• Fast algorithms for approximately counting mismatches
• \(L_{1}\) pattern matching lower bound
• Generalized String Matching
• The k-mismatch problem revisited
• Faster algorithms for string matching with k mismatches
• An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
• A Simple Algorithm for Approximating the Text-To-Pattern Hamming Distance
• Combinatorial Pattern Matching
• Combinatorial Pattern Matching

This page was built for publication: Towards Unified Approximate Pattern Matching for Hamming and L_1 Distance