SEARCHING SUBSEQUENCES

被引：53

作者：

BAEZAYATES, RA

机构：

[1] Departamento de Ciencias de la Computación, Escuela de Ingeniería, Universidad de Chile, Santiago

来源：

THEORETICAL COMPUTER SCIENCE | 1991年 / 78卷 / 02期

关键词：

D O I：

10.1016/0304-3975(91)90358-9

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We define the directed acyclic subsequence graph of a text as the smallest deterministic partial finite automaton that recognizes all possible subsequences of that text. We define the size of the automaton as the size of the transition function and not the number of states. We show that it is possible to build this automaton using O(n log n) time and O(n) space for a text of size n. With this structure, we can search a subsequence in logarithmic time. We extend this construction to the case of multiple strings obtaining a O(n2 log n) time and O(n2) space algorithm, where n is the size of the set of strings. For the later case, we discuss its application to the longest common subsequence problem.

引用

页码：363 / 376

页数：14

共 14 条

[1]

Aho A. V., 1974, DESIGN ANAL COMPUTER

[2]

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

[3] THE LONGEST COMMON SUBSEQUENCE PROBLEM REVISITED [J].

APOSTOLICO, A ;

GUERRA, C .

ALGORITHMICA, 1987, 2 (03) :315-336

[4]

BAEZAYATES RA, 1989, LECT NOTES COMPUT SC, V351, P104

[5] THE SMALLEST AUTOMATION RECOGNIZING THE SUBWORDS OF A TEXT [J].

BLUMER, A ;

BLUMER, J ;

HAUSSLER, D ;

EHRENFEUCHT, A ;

CHEN, MT ;

SEIFERAS, J .

THEORETICAL COMPUTER SCIENCE, 1985, 40 (01) :31-55

[6]

Garey M.R., 1979, COMPUTERS INTRACTABI, V174

[7] CALCULATION OF DISTANCE BY SUBSEQUENCES [J].

HEBRARD, JJ ;

CROCHEMORE, M .

RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS, 1986, 20 (04) :441-456

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

HIRSCHBERG, DS .

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

[9] COMPUTING A LONGEST COMMON SUBSEQUENCE FOR A SET OF STRINGS [J].

HSU, WJ ;

DU, MW .

BIT, 1984, 24 (01) :45-59

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

HUNT, JW ;

SZYMANSKI, TG .

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

← 1 2 →