A note on the longest common substring with k-mismatches problem

الأصل · EN

The recently introduced longest common substring with k-mismatches (k-LCF) problem is to find, given two sequences S₁ and S₂ of length n each, a longest substring A₁ of S₁ and A₂ of S₂ such that the Hamming distance between A₁ and A₂ is at most k. So far, the only subquadratic time result for this problem was known for k = 1 FGKU2014. We first present two output-dependent algorithms solving the k-LCF problem and show that for k = O(¹⁻ε n), where ε > 0, at least one of them works in subquadratic time, using O(n) words of space. The choice of one of these two algorithms to be applied for a given input can be done after linear time and space preprocessing. Finally we present a tabulation-based algorithm working, in its range of applicability, in O(n²(k+ℓ₀, σ)/ n) time, where ℓ₀ is the length of the standard longest common substring.