Matching with don't-cares and a small number of mismatches

DOI10.1016/j.ipl.2008.10.016zbMath1191.68896OpenAlexW2005830158MaRDI QIDQ976093

Ron Shamir, Chaim Linhart

Publication date: 16 June 2010

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2008.10.016

zbMATH Keywords

analysis of algorithmspattern matchingapproximate wildcard matching

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Pattern recognition, speech recognition (68T10)

Related Items

A faster algorithm for the computation of string convolutions using LZ78 parsing

Cites Work

• Unnamed Item
• Simple deterministic wildcard matching
• Matching patterns in strings subject to multi-linear transformations
• PRIMES is in P
• Approximate formulas for some functions of prime numbers
• Secure multiparty computation of approximations
• Improved Sketching of Hamming Distance with Error Correcting
• k-Mismatch with Don’t Cares
• Verifying candidate matches in sparse and wildcard matching
• Pattern matching with address errors
• Generalized String Matching
• Prime sieves using binary quadratic forms
• Faster algorithms for string matching with k mismatches