On approximate pattern matching with thresholds

DOI10.1016/J.IPL.2017.03.001zbMATH Open1405.68467OpenAlexW2594808892MaRDI QIDQ522963FDOQ522963

Peng Zhang, Mikhail J. Atallah

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

Recommendations

• Pattern matching in the Hamming distance with thresholds
• On-line approximate string matching with bounded errors
• On string matching with mismatches
• A randomized algorithm for approximate string matching
• Fast algorithms for approximately counting mismatches

zbMATH Keywords

thresholdpattern matchingrecursiondesign of algorithms

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (3)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q522963)