Circular pattern matching with k mismatches

We consider the circular pattern matching with mismatches (-CPM) problem in which one is to compute the minimal Hamming distance of every length- substring of and any cyclic rotation of , if this distance is no more than . It is a variation of the well-studied -mismatch problem. A multitude of papers has been devoted to solving the -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 -time algorithm and an -time algorithm. The latter algorithm applies in an extended way a technique that was very recently developed for the -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 to .