A Simple Algorithm for Approximating the Text-To-Pattern Hamming Distance
From MaRDI portal
Publication:5240425
DOI10.4230/OASIcs.SOSA.2018.10zbMath1433.68633OpenAlexW2783094551MaRDI QIDQ5240425
Publication date: 25 October 2019
Full work available at URL: https://doi.org/10.4230/OASIcs.SOSA.2018.10
Analysis of algorithms (68W40) Approximation algorithms (68W25) Randomized algorithms (68W20) Algorithms on strings (68W32)
Related Items
Exploiting pseudo-locality of interchange distance ⋮ Unnamed Item ⋮ Towards Unified Approximate Pattern Matching for Hamming and L_1 Distance ⋮ Approximating Approximate Pattern Matching ⋮ Recent advances in text-to-pattern distance algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Set intersection and sequence matching with mismatch counting
- Mismatch sampling
- Efficient computations of \(\ell _1\) and \(\ell _{\infty }\) rearrangement distances
- Pattern matching with don't cares and few errors
- Pattern matching with pair correlation distance
- Fast algorithms for approximately counting mismatches
- A filtering algorithm for \(k\)-mismatch with don't cares
- Pattern Matching under Polynomial Transformation
- Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
- Improved Sketching of Hamming Distance with Error Correcting
- Approximate String Matching with Address Bit Errors
- Pattern matching with address errors
- An Extension of the String-to-String Correction Problem
- An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
- Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
- Exact and Approximate Pattern Matching in the Streaming Model
- Algorithms – ESA 2004
- Combinatorial Pattern Matching
- On the Cost of Interchange Rearrangement in Strings
