Approximating Approximate Pattern Matching

DOI10.4230/LIPIcs.CPM.2019.15OpenAlexW2962979835MaRDI QIDQ5088905

Przemysław Uznański, Jan Studený

Publication date: 18 July 2022

Full work available at URL: https://arxiv.org/abs/1810.01676

zbMATH Keywords

Hamming distanceapproximation algorithmsapproximate pattern matching\(\ell_1\) distance\(\ell_p\) distance

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items

Unnamed Item ⋮ Recent advances in text-to-pattern distance algorithms

Cites Work

• Approximate pattern matching with the \(L_1\), \(L_2\) and \(L_\infty\) metrics
• Fast algorithms for approximately counting mismatches
• \(L_{1}\) pattern matching lower bound
• A Tight Lower Bound for High Frequency Moment Estimation with Small Error
• Taylor Polynomial Estimator for Estimating Frequency Moments
• 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
• Towards Unified Approximate Pattern Matching for Hamming and L_1 Distance
• Brief Announcement: Hamming Distance Completeness and Sparse Matrix Multiplication.
• Univariate Stable Distributions
• A Subquadratic Approximation Scheme for Partition
• A Simple Algorithm for Approximating the Text-To-Pattern Hamming Distance
• Combinatorial Pattern Matching
• Combinatorial Pattern Matching
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item