Linear-Time Algorithm for Long LCF with k Mismatches

2018/02/18 by Charalampopoulos, Panagiotis, Crochemore, Maxime, Iliopoulos, Costas S. +5 · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1802.06369

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. 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(ℓ) problem in which we assume that the sought factors have length at least ℓ, and the LCF_k(ℓ) problem for ℓ=Ω(log^2k+2 n), which we call the Long LCF_k problem. We use difference covers to reduce the Long LCF_k problem to a task involving m=O(n/log^k+1n) synchronized factors. The latter can be solved in O(m log^k+1m) time, which results in a linear-time algorithm for Long LCF_k. In general, our solution to LCF_k(ℓ) for arbitrary ℓ takes O(n + n log^k+1 n/√(ℓ)) time.

Cited by

• Space-Efficient k-Mismatch Text Indexes

Related

• A note on the longest common substring with k-mismatches problem
• Quasi-Linear-Time Algorithm for Longest Common Circular Factor
• Algorithms for Longest Common Abelian Factors
• Approximating the Longest Common Subsequence problem within a sub-polynomial factor in linear time
• Faster Algorithms for Longest Common Substring