TY - JOUR
T1 - Circular pattern matching with k mismatches
AU - Charalampopoulos, Panagiotis
AU - Kociumaka, Tomasz
AU - Pissis, Solon P.
AU - Radoszewski, Jakub
AU - Rytter, Wojciech
AU - Straszyński, Juliusz
AU - Waleń, Tomasz
AU - Zuba, Wiktor
PY - 2021/2
Y1 - 2021/2
N2 - 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].
AB - 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].
KW - Approximate pattern matching
KW - Circular pattern matching
KW - k-mismatch problem
UR - http://www.scopus.com/inward/record.url?scp=85088923630&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85088923630&partnerID=8YFLogxK
U2 - 10.1016/j.jcss.2020.07.003
DO - 10.1016/j.jcss.2020.07.003
M3 - Article
AN - SCOPUS:85088923630
SN - 0022-0000
VL - 115
SP - 73
EP - 85
JO - Journal of Computer and System Sciences
JF - Journal of Computer and System Sciences
ER -