EFFICIENT TWO-DIMENSIONAL PATTERN-MATCHING IN THE PRESENCE OF ERRORS

被引：19

作者：

KRITHIVASAN, K ^{[1
]}

SITALAKSHMI, R ^{[1
]}

机构：

[1] UNIV MARYLAND,CTR AUTOMAT RES,COLLEGE PK,MD 20742

来源：

INFORMATION SCIENCES | 1987年 / 43卷 / 03期

关键词：

COMPUTER PROGRAMMING - Algorithms;

D O I：

10.1016/0020-0255(87)90037-5

中图分类号：

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

学科分类号：

0812 ;

摘要：

We give an algorithm for two-dimensional pattern matching in the presence of errors. We find that the complexity of our algorithm is 0(kn//1n//2 log n//2 plus n//1**2n//2 plus kn//1m//1m//2), where the pattern is an n//1 multiplied by n//2 array, the text is an m//1 multiplied by m//2 array, and k is the number of mismatches allowed.

引用

页码：169 / 184

页数：16