Back to Search
Start Over
A space efficient algorithm for the longest common subsequence in k-length substrings.
- Source :
-
Theoretical Computer Science . Jul2017, Vol. 687, p79-92. 14p. - Publication Year :
- 2017
-
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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 687
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 123443316
- Full Text :
- https://doi.org/10.1016/j.tcs.2017.05.015