Pattern matching with don't cares and few errors

DOI10.1016/j.jcss.2009.06.002zbMath1186.68407MaRDI 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 matching; group testing; string algorithms; randomised algorithms

Mathematics Subject Classification ID

68T10: Pattern recognition, speech recognition

68W20: Randomized algorithms

Related Items

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