Circular pattern matching with k mismatches

Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis*, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, Wiktor Zuba

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

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].

Original languageEnglish
Pages (from-to)73-85
Number of pages13
JournalJournal of Computer and System Sciences
Volume115
Early online date29 Jul 2020
DOIs
Publication statusE-pub ahead of print - 29 Jul 2020

Keywords

  • Approximate pattern matching
  • Circular pattern matching
  • k-mismatch problem

Fingerprint Dive into the research topics of 'Circular pattern matching with k mismatches'. Together they form a unique fingerprint.

Cite this