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

Abstract 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.