2019-07-10

# Circular pattern matching with k mismatches

## Publication

### Publication

*Presented at the International Symposium on Fundamentals of Computation Theory (August 2019), Copenhagen, Denmark*

The k-mismatch problem consists in computing the Hamming distance between a pattern P of length m and every length-m substring of a text T of length n, if this distance is no more than k. In many real-world applications, any cyclic shift of P is a relevant pattern, and thus one is interested in computing the minimal distance of every length-m substring of T and any cyclic shift of P. This is the circular pattern matching with k mismatches (k-CPM) problem. A multitude of papers have been devoted to solving this problem but, to the best of our knowledge, only average-case upper bounds are known. In this paper, we present the first non-trivial worst-case upper bounds for the k-CPM problem. Specifically, we show an O(nk)-time algorithm and an
$O(n+\frac{n}{m}{k}^{5})$
-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., SODA 2019].

Additional Metadata | |
---|---|

doi.org/10.1007/978-3-030-25027-0_15 | |

Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence | |

International Symposium on Fundamentals of Computation Theory | |

Organisation | Centrum Wiskunde & Informatica, Amsterdam, The Netherlands |

Charalampopoulos, P, Kociumaka, T, Pissis, S, Radoszewski, J, Rytter, W, Straszyński, J, … Zuba, W. (2019). Circular pattern matching with k mismatches. In
Proceedings of Fundamentals of Computation Theory (pp. 213–228). doi:10.1007/978-3-030-25027-0_15 |