Exploiting word-level parallelism for fast convolutions and their applications in approximate string matching

DOI10.1016/j.ejc.2012.07.013zbMath1251.68306OpenAlexW1994855795MaRDI QIDQ1761497

Szymon Grabowski, Kimmo Fredriksson

Publication date: 15 November 2012

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejc.2012.07.013

zbMATH Keywords

convolutionspattern matchingapproximate string matchingword RAM model of computation

Mathematics Subject Classification ID

Related Items (5)

An acceleration of FFT-based algorithms for the match-count problem ⋮ Approximate pattern matching with \(k\)-mismatches in packed text ⋮ Rank and select operations on a word ⋮ On approximate pattern matching with thresholds ⋮ Fast Convolutions of Packed Strings and Pattern Matching with Wildcards

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On Roth's theorem on progressions
• Finding large 3-free sets. I. The small \(n\) case
• Faster pattern matching with character classes using prime number encoding
• Efficient string matching with k mismatches
• Data structures and algorithms for approximate string matching
• Surpassing the information theoretic bound with fusion trees
• An improved construction of progression-free sets
• Bit-parallel string matching under Hamming distance in \(O(n\lceil m/w\rceil)\) worst case time
• Fast Convolutions and Their Applications in Approximate String Matching
• Generalized String Matching
• Algorithms on Strings, Trees and Sequences
• Combinatorial Pattern Matching
• Combinatorial Pattern Matching
• On Certain Sets of Integers
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression

This page was built for publication: Exploiting word-level parallelism for fast convolutions and their applications in approximate string matching