|
|||||
|
|
A filtering algorithm for k-mismatch with don't cares |
|
| Authors: | Raphaël Clifford Ely Porat |
| Affiliation: | a University of Bristol, Dept. of Computer Science, Bristol, BS8 1UB, UK b Bar-Ilan University, Dept. of Computer Science, 52900 Ramat-Gan, Israel |
| Abstract: | 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 Θ(nm1/3k1/3log2/3m) time. |
| Keywords: | Algorithms Design of algorithms Combinatorial problems String algorithms Don't cares Pattern matching Filtering Fast Fourier transforms |
| 本文献已被 ScienceDirect 等数据库收录！ | |