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

DOI10.1016/j.ejc.2012.07.013zbMath1251.68306MaRDI 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

convolutions; pattern matching; approximate string matching; word RAM model of computation

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

68R05: Combinatorics in computer science

Related Items

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

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