Circular pattern matching with k mismatches
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) . A preliminary version of this work appeared at FCT 2019 . In this version we improve the time complexity of the second algorithm from [Formula presented] to [Formula presented].
|Approximate pattern matching, Circular pattern matching, k-mismatch problem|
|Journal of Computer and System Sciences|
|Organisation||Centrum Wiskunde & Informatica, Amsterdam, 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