The longest common substring with k -mismatches problem is to find, given two strings S1S1 and S2S2, a longest substring A1A1 of S1S1 and A2A2 of S2S2 such that the Hamming distance between A1A1 and A2A2 is ≤k . We introduce a practical O(nm)O(nm) time and O(1)O(1) space solution for this problem, where n and m are the lengths of S1S1 and S2S2, respectively. This algorithm can also be used to compute the matching statistics with k -mismatches of S1S1 and S2S2 in O(nm)O(nm) time and O(m)O(m) space. Moreover, we also present a theoretical solution for the k=1k=1 case which runs in O(nlogm)O(nlogm) time, assuming m≤nm≤n, and uses O(m)O(m) space, improving over the existing O(nm)O(nm) time and O(m)O(m) space bound of Babenko and Starikovskaya.
|Journal||Information Processing Letters|
|Publication status||Published - 2015|
|MoE publication type||A1 Journal article-refereed|
- Combinatorial problems, Hamming distance, Longest common substring, String algorithms