Name
Abstract | ||
|---|---|---|
We present solutions 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 and a bound k, our algorithms find all the places that the pattern matches the text with at most k mismatches. We first give a @Q(n(k+logmlogk)logn) time randomised algorithm which finds the correct answer with high probability. We then present a new deterministic @Q(nk^2log^2m) time solution that uses tools originally developed for group testing. Taking our derandomisation approach further we develop an approach based on k-selectors that runs in @Q(nkpolylogm) time. Further, in each case the location of the mismatches at each alignment is also given at no extra cost. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.jcss.2009.06.002 | J. Comput. Syst. Sci. |
Keywords | DocType | Volume |
bound k,pattern p,k-mismatch pattern,length n,randomised algorithms,time solution,pattern matching,time randomised algorithm,length m,string algorithms,group testing,k mismatches,present solution,derandomisation approach | Journal | 76 |
Issue | ISSN | Citations |
2 | Journal of Computer and System Sciences | 7 |
PageRank | References | Authors |
0.60 | 26 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Raphaël Clifford | 1 | 268 | 28.57 |
| Klim Efremenko | 2 | 135 | 15.31 |
| ely porat | 3 | 1007 | 79.16 |
| Amir Rothschild | 4 | 49 | 3.46 |