Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2018.23
URN: urn:nbn:de:0030-drops-86869
URL: https://drops.dagstuhl.de/opus/volltexte/2018/8686/
Charalampopoulos, Panagiotis ; Crochemore, Maxime ; Iliopoulos, Costas S. ; Kociumaka, Tomasz ; Pissis, Solon P. ; Radoszewski, Jakub ; Rytter, Wojciech ; Walen, Tomasz
Linear-Time Algorithm for Long LCF with k Mismatches
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{charalampopoulos_et_al:LIPIcs:2018:8686,
author = {Panagiotis Charalampopoulos and Maxime Crochemore and Costas S. Iliopoulos and Tomasz Kociumaka and Solon P. Pissis and Jakub Radoszewski and Wojciech Rytter and Tomasz Walen},
title = {{Linear-Time Algorithm for Long LCF with k Mismatches}},
booktitle = {Annual Symposium on Combinatorial Pattern Matching (CPM 2018)},
pages = {23:1--23:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-074-3},
ISSN = {1868-8969},
year = {2018},
volume = {105},
editor = {Gonzalo Navarro and David Sankoff and Binhai Zhu},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2018/8686},
URN = {urn:nbn:de:0030-drops-86869},
doi = {10.4230/LIPIcs.CPM.2018.23},
annote = {Keywords: longest common factor, longest common substring, Hamming distance, heavy-light decomposition, difference cover}
}
| Keywords: | longest common factor, longest common substring, Hamming distance, heavy-light decomposition, difference cover | |
| Seminar: | Annual Symposium on Combinatorial Pattern Matching (CPM 2018) | |
| Issue date: | 2018 | |
| Date of publication: | 18.05.2018 |
