Faster pattern matching with character classes using prime number encoding

DOI10.1016/J.JCSS.2008.08.005MaRDI QIDQ1004281zbMATH OpenOpenAlexFDO

Authors Chaim Linhart, Ron Shamir

Publication date 2 March 2009

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2008.08.005

zbMATH Keywords

Hamming distanceFFT-based pattern matchingpattern matching with character classessubset matching

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10) Analysis of algorithms (68W40) Searching and sorting (68P10) Nonnumerical algorithms (68W05) Approximation algorithms (68W25)

Recommendations

• Pattern matching with wildcards using words of shorter length
• Modulated string searching
• Fast convolutions of packed strings and pattern matching with wildcards
• Fast practical multi-pattern matching
• Designing optimal- and fast-on-average pattern matching algorithms

Cites work

• scientific article; zbMATH DE number 3949728 (Why is no real title available?)
• scientific article; zbMATH DE number 3471577 (Why is no real title available?)
• scientific article; zbMATH DE number 1559523 (Why is no real title available?)
• scientific article; zbMATH DE number 2119723 (Why is no real title available?)
• scientific article; zbMATH DE number 1445379 (Why is no real title available?)
• A fast string searching algorithm
• Algorithms on Strings, Trees and Sequences
• Approximate formulas for some functions of prime numbers
• Fast Pattern Matching in Strings
• Generalized String Matching
• Introduction to algorithms
• PRIMES is in P
• Prime sieves using binary quadratic forms
• Simple deterministic wildcard matching
• The p53MH algorithm and its application in detecting p53-responsive genes
• Verifying candidate matches in sparse and wildcard matching

Cited in

(8)

• Space lower bounds for online pattern matching
• Modulated string searching
• Exploiting word-level parallelism for fast convolutions and their applications in approximate string matching
• An acceleration of FFT-based algorithms for the match-count problem
• Pattern matching with wildcards using words of shorter length
• Fast convolutions of packed strings and pattern matching with wildcards
• Multi-pattern matching algorithm with wildcards based on bit-parallelism
• Space Lower Bounds for Online Pattern Matching

This page was built for publication: Faster pattern matching with character classes using prime number encoding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1004281)