Faster pattern matching with character classes using prime number encoding

DOI10.1016/j.jcss.2008.08.005zbMath1169.68044OpenAlexW2020266312MaRDI QIDQ1004281

Ron Shamir, Chaim Linhart

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

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

Related Items (7)

Pattern matching with wildcards using words of shorter length ⋮ Space lower bounds for online pattern matching ⋮ Modulated string searching ⋮ Multi-pattern matching algorithm with wildcards based on bit-parallelism ⋮ Space Lower Bounds for Online Pattern Matching ⋮ Exploiting word-level parallelism for fast convolutions and their applications in approximate string matching ⋮ Fast Convolutions of Packed Strings and Pattern Matching with Wildcards

Cites Work

• Simple deterministic wildcard matching
• PRIMES is in P
• Approximate formulas for some functions of prime numbers
• A fast string searching algorithm
• Verifying candidate matches in sparse and wildcard matching
• Generalized String Matching
• Fast Pattern Matching in Strings
• Algorithms on Strings, Trees and Sequences
• Prime sieves using binary quadratic forms
• The p53MH algorithm and its application in detecting p53-responsive genes
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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