On approximate pattern matching with thresholds

DOI10.1016/j.ipl.2017.03.001zbMath1405.68467OpenAlexW2594808892MaRDI QIDQ522963

Mikhail J. Atallah, Peng Zhang

Publication date: 20 April 2017

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2017.03.001

zbMATH Keywords

recursiondesign of algorithmspattern matchingthreshold

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Randomized algorithms (68W20) Algorithms on strings (68W32)

Related Items (3)

Brief Announcement: Hamming Distance Completeness and Sparse Matrix Multiplication. ⋮ Hamming Distance Completeness ⋮ Recent advances in text-to-pattern distance algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On special families of morphisms related to \(\delta \)-matching and don't care symbols
• Fast algorithms for approximately counting mismatches
• Exploiting word-level parallelism for fast convolutions and their applications in approximate string matching
• Pattern matching in the Hamming distance with thresholds
• Bit-parallel string matching under Hamming distance in \(O(n\lceil m/w\rceil)\) worst case time
• A lower-variance randomized algorithm for approximate string matching
• EFFICIENT ALGORITHMS FOR (δ,γ,α) AND (δ, k_Δ, α)-MATCHING
• Generalized String Matching
• Combinatorial Pattern Matching
• A randomized algorithm for approximate string matching

This page was built for publication: On approximate pattern matching with thresholds