Pattern matching with don't cares and few errors

DOI10.1016/j.jcss.2009.06.002zbMath1186.68407OpenAlexW2049842402MaRDI QIDQ847263

Klim Efremenko, Raphaël Clifford, Ely Porat, Amir Rothschild

Publication date: 12 February 2010

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

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2009/2244/

zbMATH Keywords

pattern matchinggroup testingstring algorithmsrandomised algorithms

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10) Randomized algorithms (68W20)

Related Items

Generalized framework for group testing: queries, feedbacks and adversaries, On pattern matching with \(k\) mismatches and few don't cares, On the average-case complexity of pattern matching with wildcards, Bounds and algorithms for generalized superimposed codes, Unnamed Item, A Simple Algorithm for Approximating the Text-To-Pattern Hamming Distance, Towards Optimal Approximate Streaming Pattern Matching by Matching Multiple Patterns in Multiple Streams, Streaming pattern matching with \(d\) wildcards, Subquadratic non-adaptive threshold group testing, Low-weight superimposed codes and related combinatorial structures: bounds and applications, Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard

Uses Software

• AETG

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Simple deterministic wildcard matching
• Efficient string matching with k mismatches
• Fast algorithms for approximately counting mismatches
• Distributed broadcast in radio networks of unknown topology.
• A filtering algorithm for \(k\)-mismatch with don't cares
• A fast string searching algorithm
• Explicit Non-adaptive Combinatorial Group Testing Schemes
• Verifying candidate matches in sparse and wildcard matching
• Dictionary matching and indexing with errors and don't cares
• Born again group testing: Multiaccess communications
• Generalized String Matching
• Fast Pattern Matching in Strings
• Maximally Efficient Two‐Stage Screening
• Faster algorithms for string matching with k mismatches
• A Linear Size Index for Approximate Pattern Matching
• Nonrandom binary superimposed codes
• Fundamentals of Computation Theory