ON THE SPACE COMPLEXITY OF SOME ALGORITHMS FOR SEQUENCE COMPARISON

被引：1

作者：

RABANI, Y ^{[1
]}

GALIL, Z ^{[1
]}

机构：

[1] COLUMBIA UNIV,DEPT COMP SCI,NEW YORK,NY 10027

来源：

THEORETICAL COMPUTER SCIENCE | 1992年 / 95卷 / 02期

关键词：

D O I：

10.1016/0304-3975(92)90266-I

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Recent algorithms for computing the modified edit distance given convex or concave gap cost functions are shown to require OMEGA(n2) space for certain input.

引用

页码：231 / 244

页数：14