Bit-parallel string matching under Hamming distance in O(n m/w) worst case time

DOI10.1016/J.IPL.2007.08.021MaRDI QIDQ2380069zbMATH OpenOpenAlexFDO

Authors Szymon Grabowski, Kimmo Fredriksson

Publication date 24 March 2010

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

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

zbMATH Keywords

algorithmsHamming distanceapproximate string matchingbit-parallelism

Mathematics Subject Classification ID

Searching and sorting (68P10) Nonnumerical algorithms (68W05)

Recommendations

• scientific article; zbMATH DE number 1445379
• On string matching with mismatches
• Faster algorithms for string matching with k mismatches
• Simple and efficient string matching with k mismatches
• Nested Counters in Bit-Parallel String Matching

Cites work

• scientific article; zbMATH DE number 3984596 (Why is no real title available?)
• scientific article; zbMATH DE number 140453 (Why is no real title available?)
• scientific article; zbMATH DE number 3471577 (Why is no real title available?)
• scientific article; zbMATH DE number 1445379 (Why is no real title available?)
• A fast bit-vector algorithm for approximate string matching based on dynamic programming
• Bit-parallel (\(\delta ,\gamma\))-matching and suffix automata

Cited in

(15)

• Simple and efficient string matching with k mismatches
• Bit-parallel witnesses and their applications to approximate string matching
• Approximate pattern matching with \(k\)-mismatches in packed text
• scientific article; zbMATH DE number 7650314 (Why is no real title available?)
• Exploiting word-level parallelism for fast convolutions and their applications in approximate string matching
• Pattern matching in the Hamming distance with thresholds
• Average-optimal string matching
• On the Efficiency of the Hamming C-Centerstring Problems
• A linear-time algorithm for Hamming distance with shifts
• Nested Counters in Bit-Parallel String Matching
• On finding \(k\)-cliques in \(k\)-partite graphs
• Fast identification of heavy hitters by cached and packed group testing
• Fast convolutions and their applications in approximate string matching
• Bit-Parallel Approximate Matching of Circular Strings with k Mismatches
• On approximate pattern matching with thresholds

This page was built for publication: Bit-parallel string matching under Hamming distance in \(O(n\lceil m/w\rceil)\) worst case time

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