2021-02-01
Circular pattern matching with k mismatches
Publication
Publication
Journal of Computer and System Sciences , Volume 115 p. 73- 85
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 [Formula presented]-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]. A preliminary version of this work appeared at FCT 2019 [35]. In this version we improve the time complexity of the second algorithm from [Formula presented] to [Formula presented].
| Additional Metadata | |
|---|---|
| , , | |
| doi.org/10.1016/j.jcss.2020.07.003 | |
| Journal of Computer and System Sciences | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Charalampopoulos, P., Kociumaka, T., Pissis, S., Radoszewski, J., Rytter, W., Straszyński, J., … Zuba, W. (2021). Circular pattern matching with k mismatches. Journal of Computer and System Sciences, 115, 73–85. doi:10.1016/j.jcss.2020.07.003 |
|
