Simple and fast linear space computation of longest common subsequences

被引：15

作者：

Rick, C ^{[1
]}

机构：

[1] Univ Bonn, Inst Informat 4, D-53117 Bonn, Germany

来源：

INFORMATION PROCESSING LETTERS | 2000年 / 75卷 / 06期

关键词：

algorithms; longest common subsequence; linear space;

D O I：

10.1016/S0020-0190(00)00114-9

中图分类号：

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

学科分类号：

0812 ;

摘要：

The longest common subsequence (LCS) problem is to find a sequence of greatest largest possible length that can be obtained from two sequences, A = a1a2...am and B = b1b2...bn, where m≤n, by deleting zero or more, not necessarily adjacent, symbols. It is shown how to maintain the O(min{pm,p(n-p)}) time complexity and linear space algorithm. All linear space implementations rely on variations of a divide and conquer sequence.

引用

页码：275 / 281

页数：7

共 13 条

[1]

Apostolico A., 1985, Proceedings of the Twenty-third Annual Allerton Conference on Communication, Control, and Computing, P76

[2] FAST LINEAR-SPACE COMPUTATIONS OF LONGEST COMMON SUBSEQUENCES [J].

APOSTOLICO, A ;

BROWNE, S ;

GUERRA, C .

THEORETICAL COMPUTER SCIENCE, 1992, 92 (01) :3-17

[3]

Apostolico A., 1997, HDB FORMAL LANGUAGES, P361, DOI DOI 10.1007/978-3-662-07675-0_8

[4]

Goeman H., 1999, Proceedings of the Prague Stringology Club Workshop '99, P40

[5]

Hirschberg Daniel S., 1997, PATTERN MATCHING ALG, P123

[6] ALGORITHMS FOR LONGEST COMMON SUBSEQUENCE PROBLEM [J].

HIRSCHBERG, DS .

JOURNAL OF THE ACM, 1977, 24 (04) :664-675

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

HIRSCHBERG, DS .

COMMUNICATIONS OF THE ACM, 1975, 18 (06) :341-343

[8]

KUMAR SK, 1987, ACTA INFORM, V24, P353, DOI 10.1007/BF00265993

[9] An O(ND) Difference Algorithm and Its Variations [J].

Myers, Eugene W. .

ALGORITHMICA, 1986, 1 (1-4) :251-266

[10] OPTIMAL ALIGNMENTS IN LINEAR-SPACE [J].

MYERS, EW ;

MILLER, W .

COMPUTER APPLICATIONS IN THE BIOSCIENCES, 1988, 4 (01) :11-17

← 1 2 →