Name
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 @Q(nm^1^/^3k^1^/^3log^2^/^3m) time. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.ipl.2010.08.012 | Inf. Process. Lett. |
Keywords | Field | DocType |
k-mismatch pattern,length n,k mismatches,bound k,pattern p,length m,pattern matching | Computer science,Filter (signal processing),Algorithm,Pattern matching | Journal |
Volume | Issue | ISSN |
110 | 22 | 0020-0190 |
Citations | PageRank | References |
4 | 0.43 | 13 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Raphaël Clifford | 1 | 268 | 28.57 |
| ely porat | 2 | 1007 | 79.16 |