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

Two space efficient algorithms to solve the LCSk problem and LCS≥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 LCSk problem is reduced from O(n2) to O(kn), if the size of the two input sequences are both n. The time and space costs of the second algorithm to solve the LCS≥k problem are both improved. The time cost is reduced from O(kn2) to O(n2), and the space cost is reduced from O(n2) to O(kn). In the case of k=O(1), the two algorithms are both linear space algorithms.