A space efficient algorithm for the longest common subsequence in k-length substrings

Two space efficient algorithms to solve the L C S k problem and L C S ≥ k problem are presented in this paper. The algorithms improve the time and space complexities of the algorithms of Benson et al. [4]. The space cost of the first algorithm to solve the L C S k problem is reduced from O ( n 2 ) to O ( k n ), if the size of the two input sequences are both n. The time and space costs of the second algorithm to solve the L C S ≥ k problem are both improved. The time cost is reduced from O ( k n 2 ) to O ( n 2 ), and the space cost is reduced from O ( n 2 ) to O ( k n ). In the case of k = O ( 1 ), the two algorithms are both linear space algorithms.

Authors

• Daxin Zhu Quanzhou Normal University
• Lei Wang
• Tinran Wang
• Xiaodong Wang Microsoft Research Asia

Keywords

• Longest common subsequence
• Similarity of strings
• Edit distance
• Dynamic programming