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

作者：Grabowski Szymon^*

来源：Information Processing Letters, 2015, 115(6-8): 640-642.

DOI：10.1016/j.ipl.2015.03.003

• Combinatorial problems
• String algorithms
• Longest common substring with k-mismatches
• Word-level parallelism

The recently introduced longest common substring with k-mismatches (k-LCF) problem is to find, given two sequences S-1 and S-2 of length n each, a longest substring A(1) of S-1 and A(2) of S-2 such that the Hamming distance between A(1) and A(2) is at most k. So far, the only subquadratic time result for this problem was known for k = 1 [5]. We present two output-dependent algorithms solving the k-LCF problem and show that for k = O (log(1-epsilon) n), where epsilon > 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.

• 出版日期2015-8