2026-07-23T20:59:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8686 2024-03-06T10:43:03Z ddc:004 open_access

Linear-Time Algorithm for Long LCF with k Mismatches Charalampopoulos, Panagiotis Crochemore, Maxime Iliopoulos, Costas S. Kociumaka, Tomasz Pissis, Solon P. Radoszewski, Jakub Rytter, Wojciech Walen, Tomasz longest common factor longest common substring Hamming distance heavy-light decomposition difference cover 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik 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 2018 Is Part Of LIPIcs, Volume 105, 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2018.23 urn:nbn:de:0030-drops-86869 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2018.23 eng https://creativecommons.org/licenses/by/3.0/legalcode