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 - 2020/7/29

Y1 - 2020/7/29

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

VL - 115

SP - 73

EP - 85

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

SN - 0022-0000

ER -