Matching for run-length encoded strings

被引：37

作者：

Apostolico, A

Landau, GM

Skiena, S

机构：

[1] Purdue Univ, Dept Comp Sci, W Lafayette, IN 47907 USA

[2] Univ Padua, Dipartimento Elettron & Informat, I-35131 Padua, Italy

[3] Polytech Univ, Dept Comp & Informat Sci, Brooklyn, NY 11201 USA

[4] Univ Haifa, Dept Comp Sci, IL-31905 Haifa, Israel

[5] SUNY Stony Brook, Dept Comp Sci, Stony Brook, NY 11794 USA

来源：

JOURNAL OF COMPLEXITY | 1999年 / 15卷 / 01期

基金：

美国国家科学基金会; 英国工程与自然科学研究理事会;

关键词：

D O I：

10.1006/jcom.1998.0493

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

[No abstract available]

引用

页码：4 / 16

页数：13

共 10 条

[1]

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

[2]

APOSTOLICO A, 1996, HDB FORMAL LANGUAGES, V2, P361

[3] AN IMPROVED ALGORITHM FOR COMPUTING THE EDIT DISTANCE OF RUN-LENGTH CODED STRINGS [J].

BUNKE, H ;

CSIRIK, J .

INFORMATION PROCESSING LETTERS, 1995, 54 (02) :93-96

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

HIRSCHBERG, DS .

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

[5] THE SET-SET LCS PROBLEM [J].

HIRSCHBERG, DS ;

LARMORE, LL .

ALGORITHMICA, 1989, 4 (04) :503-510

[6] INFORMATION-THEORETIC LOWER BOUND FOR LONGEST COMMON SUBSEQUENCE PROBLEM [J].

HIRSCHBERG, DS .

INFORMATION PROCESSING LETTERS, 1978, 7 (01) :40-41

[7] A FASTER ALGORITHM COMPUTING STRING EDIT DISTANCES [J].

MASEK, WJ ;

PATERSON, MS .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1980, 20 (01) :18-31

[8]

Mitchell J.S.B., 1997, GEOMETRIC SHORTEST P

[9]

SAZAKLIS G, 1997, P 13 ACM S COMP GEOM

[10] ON THE SET LCS AND SET SET LCS PROBLEMS [J].

WANG, BF ;

CHEN, GH ;

PARK, K .

JOURNAL OF ALGORITHMS, 1993, 14 (03) :466-477

← 1 →