License: 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8686/
Go to the corresponding LIPIcs Volume Portal

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:
LIPIcs-CPM-2018-23.pdf (0.6 MB)

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
Collection: Annual Symposium on Combinatorial Pattern Matching (CPM 2018)
Issue Date: 2018
Date of publication: 18.05.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI