A filtering algorithm for k-mismatch with don't cares

We present a filtering based algorithm for the k-mismatch pattern matching problem with don't cares. Given a text t of length n and a pattern p of length m with don't care symbols in either p or t (but not both), and a bound k, our algorithm finds all the places that the pattern matches th...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2010-10, Vol.110 (22), p.1021-1025
Main Authors: Clifford, Raphaël, Porat, Ely
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Combinatorial problems
Computer science
control theory
systems
Design of algorithms
Don't cares
Exact sciences and technology
Fast Fourier transforms
Filtering
Filtration
Matching
Miscellaneous
Pattern matching
String algorithms
Studies
Symbols
Texts
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present a filtering based algorithm for the k-mismatch pattern matching problem with don't cares. Given a text t of length n and a pattern p of length m with don't care symbols in either p or t (but not both), and a bound k, our algorithm finds all the places that the pattern matches the text with at most k mismatches. The algorithm is deterministic and runs in Θ ( n m 1 / 3 k 1 / 3 log 2 / 3 m ) time. ► Faster filtering for pattern matching with don't cares. ► Approximate matching with wildcards can be achieved using filtering techniques. ► Uniform sampling of mismatches solved using filtering and randomised algorithms.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2010.08.012