A BIT-STRING LONGEST-COMMON-SUBSEQUENCE ALGORITHM

被引：70

作者：

ALLISON, L

DIX, TI

机构：

[1] Univ of Western Australia, Nedlands, Aust, Univ of Western Australia, Nedlands, Aust

来源：

INFORMATION PROCESSING LETTERS | 1986年 / 23卷 / 06期

关键词：

D O I：

10.1016/0020-0190(86)90091-8

中图分类号：

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

学科分类号：

0812 ;

摘要：

A longest-common-subsequence algorithm is described which operates in terms of bit or bit-string operations. It offers a speedup of the order of the word-length on a conventional computer.

引用

页码：305 / 310

页数：6

共 13 条

[1]

AHO AV, 1976, J ACM, V23, P1, DOI 10.1145/321921.321922

[2]

[Anonymous], COMMUN A C N

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

HIRSCHBERG, DS .

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

[4] FAST ALGORITHM FOR COMPUTING LONGEST COMMON SUBSEQUENCES [J].

HUNT, JW ;

SZYMANSKI, TG .

COMMUNICATIONS OF THE ACM, 1977, 20 (05) :350-353

[5]

MASEK WJ, 1983, TIME WARPS STRING ED

[6]

NAKATSU N, 1982, ACTA INFORM, V18, P171, DOI 10.1007/BF00264437

[7]

Reingold E. M., 1977, COMBINATORIAL ALGORI

[8]

Sankoff D., 1983, TIME WARPS STRING ED

[9]

Sellers P., 1980, J ALGORITHMS, V1, P359, DOI DOI 10.1016/0196-6774(80)90016-4

[10] THEORY AND COMPUTATION OF EVOLUTIONARY DISTANCES [J].

SELLERS, PH .

SIAM JOURNAL ON APPLIED MATHEMATICS, 1974, 26 (04) :787-793

← 1 2 →