Name
Abstract | ||
|---|---|---|
In the Longest Common Factor with k Mismatches (LCF_k) problem, we are given two strings X and Y of total length n, and we are asked to find a pair of maximal-length factors, one of X and the other of Y, such that their Hamming distance is at most k. Thankachan et al. [Thankachan et al. 2016] show that this problem can be solved in O(n log^k n) time and O(n) space for constant k. We consider the LCF_k(l) problem in which we assume that the sought factors have length at least l. We use difference covers to reduce the LCF_k(l) problem with l=Omega(log^{2k+2}n) to a task involving m=O(n/log^{k+1}n) synchronized factors. The latter can be solved in O(m log^{k+1}m) time, which results in a linear-time algorithm for LCF_k(l) with l=Omega(log^{2k+2}n). In general, our solution to the LCF_k(l) problem for arbitrary l takes O(n + n log^{k+1} n/sqrt{l}) time. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.4230/LIPIcs.CPM.2018.23 | CPM |
DocType | Volume | Citations |
Conference | abs/1802.06369 | 3 |
PageRank | References | Authors |
0.41 | 6 | 8 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Panagiotis Charalampopoulos | 1 | 3 | 4.12 |
| Maxime Crochemore | 2 | 2655 | 281.75 |
| Costas S. Iliopoulos | 3 | 1534 | 167.43 |
| Tomasz Kociumaka | 4 | 217 | 38.57 |
| Solon P. Pissis | 5 | 281 | 57.09 |
| Jakub Radoszewski | 6 | 624 | 50.36 |
| Wojciech Rytter | 7 | 2290 | 181.52 |
| Tomasz Walen | 8 | 3 | 0.74 |