Name
Abstract | ||
|---|---|---|
We consider the circular pattern matching with k mismatches (k-CPM) problem in which one is to compute the minimal Hamming distance of every length-m substring of T and any cyclic rotation of P, if this distance is no more than k. It is a variation of the well-studied k-mismatch problem. A multitude of papers has been devoted to solving the k-CPM problem, but only average-case upper bounds are known. In this paper, we present the first non-trivial worst-case upper bounds for this problem. Specifically, we show an O(nk)-time algorithm and an O(n+nmk4)-time algorithm. The latter algorithm applies in an extended way a technique that was very recently developed for the k-mismatch problem Bringmann et al. (2019) [10]. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1016/j.jcss.2020.07.003 | Journal of Computer and System Sciences |
Keywords | DocType | Volume |
Circular pattern matching,k-mismatch problem,Approximate pattern matching | Journal | 115 |
ISSN | Citations | PageRank |
0022-0000 | 0 | 0.34 |
References | Authors | |
0 | 8 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Panagiotis Charalampopoulos | 1 | 29 | 9.41 |
| Tomasz Kociumaka | 2 | 217 | 38.57 |
| Solon P. Pissis | 3 | 281 | 57.09 |
| Jakub Radoszewski | 4 | 624 | 50.36 |
| wojciech rytter | 5 | 130 | 17.13 |
| Juliusz Straszynski | 6 | 2 | 5.15 |
| Tomasz Waleń | 7 | 706 | 39.62 |
| Wiktor Zuba | 8 | 0 | 1.69 |