Longest Common Subsequence in k Length Substrings

被引：0

作者：

Benson, Gary ^{[1
]}

Levy, Avivit ^{[2
]}

Shalom, B. Riva ^{[2
]}

机构：

[1] Boston Univ, Dept Comp Sci, 111 Cummington St, Boston, MA 02215 USA

[2] Shenkar Coll, Dept Software Engn, IL-52526 Ramat Gan, Israel

来源：

SIMILARITY SEARCH AND APPLICATIONS (SISAP) | 2013年 / 8199卷

关键词：

Longest Common Subsequence; Similarity of strings; Dynamic Programming; ALGORITHM; ALIGNMENT; LCS;

D O I：

暂无

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper we define a new problem, motivated by computational biology, LCSk aiming at finding the maximal number of k length substrings, matching in both input string while preserving their order of appearance in the input strings. The traditional LCS definition is a spacial case of our problem, where k = 1. We provide an algorithm, solving the general case in O(n(2)) time, where n is the length of the input, equaling the time required for the special case of k = 1. The space requirement is O(kn). In order to enable backtracking of the solution O(n(2)) space is needed.

引用

页码：257 / 265

页数：9

共 18 条

[11] LINEAR SPACE ALGORITHM FOR COMPUTING MAXIMAL COMMON SUBSEQUENCES [J].