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

DOI10.1016/J.IPL.2007.08.021zbMATH Open1184.68209OpenAlexW2166943643MaRDI QIDQ2380069FDOQ2380069

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

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

zbMATH Keywords

algorithmsHamming distanceapproximate string matchingbit-parallelism

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A fast bit-vector algorithm for approximate string matching based on dynamic programming
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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)