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

被引：1

作者：

Zhu, Daxin ^{[1
]}

Wang, Lei ^{[2
]}

Wang, Tinran

Wang, Xiaodong ^{[3
]}

机构：

[1] Quanzhou Normal Univ, Quanzhou, Peoples R China

[2] Facebook, 1 Hacker Way, Menlo Pk, CA 94052 USA

[3] Fujian Univ Technol, Fuzhou, Peoples R China

来源：

THEORETICAL COMPUTER SCIENCE | 2017年 / 687卷

关键词：

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

D O I：

10.1016/j.tcs.2017.05.015

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 (n(2)) 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 (kn(2)) to O (n(2)), and the space cost is reduced from O (n(2)) to O (kn). In the case of k = O(1), the two algorithms are both linear space algorithms. (C) 2017 Elsevier B.V. All rights reserved.

引用

页码：79 / 92

页数：14

共 19 条

[1] Weighted LCS [J].