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

DOI10.1016/J.IPL.2007.08.021zbMath1184.68209OpenAlexW2166943643MaRDI QIDQ2380069

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)

Related Items (7)

On finding \(k\)-cliques in \(k\)-partite graphs ⋮ Pattern matching in the Hamming distance with thresholds ⋮ Approximate pattern matching with \(k\)-mismatches in packed text ⋮ On approximate pattern matching with thresholds ⋮ Exploiting word-level parallelism for fast convolutions and their applications in approximate string matching ⋮ Nested Counters in Bit-Parallel String Matching ⋮ Average-optimal string matching

Cites Work

• Bit-parallel (\(\delta ,\gamma\))-matching and suffix automata
• A fast bit-vector algorithm for approximate string matching based on dynamic programming
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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