Approximate pattern matching with \(k\)-mismatches in packed text

DOI10.1016/j.ipl.2013.07.002zbMath1284.68699arXiv1211.5433OpenAlexW2005178327MaRDI QIDQ2445229

Emanuele Giaquinta, Szymon Grabowski, Kimmo Fredriksson

Publication date: 14 April 2014

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

Full work available at URL: https://arxiv.org/abs/1211.5433

zbMATH Keywords

combinatorial problemsHamming distancestring algorithmsword-level parallelism\(k\)-mismatches

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Related Items (2)

Approximate pattern matching with \(k\)-mismatches in packed text ⋮ A note on the longest common substring with \(k\)-mismatches problem

Cites Work

• Unnamed Item
• Unnamed Item
• Fast searching in packed strings
• Fusion trees can be implemented with \(AC^0\) instructions only
• Exploiting word-level parallelism for fast convolutions and their applications in approximate string matching
• Bit-parallel string matching under Hamming distance in \(O(n\lceil m/w\rceil)\) worst case time
• Approximate pattern matching with \(k\)-mismatches in packed text
• Constant-Time Word-Size String Matching
• Increased bit-parallelism for approximate and multiple string matching
• Algorithms For Computing Approximate Repetitions In Musical Sequences
• Faster algorithms for string matching with k mismatches
• Combinatorial Pattern Matching

This page was built for publication: Approximate pattern matching with \(k\)-mismatches in packed text