TY - GEN
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 - 2019/1/1
Y1 - 2019/1/1
N2 - 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 (formula presented)-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., SODA 2019].
AB - 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 (formula presented)-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., SODA 2019].
UR - https://www.scopus.com/pages/publications/85070649596
UR - https://www.scopus.com/pages/publications/85070649596#tab=citedBy
U2 - 10.1007/978-3-030-25027-0_15
DO - 10.1007/978-3-030-25027-0_15
M3 - Conference contribution
AN - SCOPUS:85070649596
SN - 9783030250263
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 213
EP - 228
BT - Fundamentals of Computation Theory - 22nd International Symposium, FCT 2019, Proceedings
A2 - Gąsieniec, Leszek Antoni
A2 - Jansson, Jesper
A2 - Levcopoulos, Christos
PB - Springer Verlag
T2 - 22nd International Symposium on Fundamentals of Computation Theory, FCT 2019
Y2 - 12 August 2019 through 14 August 2019
ER -