On approximate pattern matching with thresholds

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

Authors 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

thresholdpattern matchingrecursiondesign of algorithms

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(6)

• Pattern matching in the Hamming distance with thresholds
• Shift finding in sub-linear time
• A graph approach to the threshold all-against-all substring matching problem
• Brief announcement: Hamming distance completeness and sparse matrix multiplication
• Recent advances in text-to-pattern distance algorithms
• 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)