Name
Abstract | ||
|---|---|---|
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}\,{\small 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]. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/978-3-030-25027-0_15 | FCT |
Field | DocType | Citations |
Discrete mathematics,Combinatorics,Substring,Computer science,Hamming distance,Pattern matching,Cyclic shift | Conference | 0 |
PageRank | References | Authors |
0.34 | 0 | 8 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Panagiotis Charalampopoulos | 1 | 3 | 4.12 |
| Tomasz Kociumaka | 2 | 217 | 38.57 |
| Solon P. Pissis | 3 | 281 | 57.09 |
| Jakub Radoszewski | 4 | 624 | 50.36 |
| Wojciech Rytter | 5 | 2290 | 181.52 |
| Juliusz Straszynski | 6 | 2 | 5.15 |
| Tomasz Walen | 7 | 3 | 0.74 |
| Wiktor Zuba | 8 | 1 | 5.13 |