FAST 2-DIMENSIONAL PATTERN-MATCHING

被引：20

作者：

BAEZAYATES, R ^{[1
]}

REGNIER, M ^{[1
]}

机构：

[1] INRIA,F-78153 LE CHESNAY,FRANCE

来源：

INFORMATION PROCESSING LETTERS | 1993年 / 45卷 / 01期

关键词：

D O I：

10.1016/0020-0190(93)90250-D

中图分类号：

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

学科分类号：

0812 ;

摘要：

An algorithm for searching for a two-dimensional m X m pattern in a two-dimensional n x n text is presented. It performs on the average less comparisons than the size of the text: n2/m using m2 extra space. Basically, it uses multiple string matching on only n/m rows of the text. It runs in at most 2n2 time and is close to the optimal n2 time for many patterns. It steadily extends to an alphabet-independent algorithm with a similar worst case. Experimental results are included for a practical version.

引用

页码：51 / 57

页数：7

共 15 条

[1] EFFICIENT STRING MATCHING - AID TO BIBLIOGRAPHIC SEARCH
AHO, AV
CORASICK, MJ
[J]. COMMUNICATIONS OF THE ACM, 1975, 18 (06) : 333 - 340
[2] Amir A., 1992, Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, P59, DOI 10.1145/129712.129719
[3] BAEZAYATES R, 1990, LECT NOTES COMPUT SC, V447, P332
[4] BAEZAYATES RA, 1989, CS8917 U WAT DEP COM
[5] TECHNIQUE FOR EXTENDING RAPID EXACT-MATCH STRING MATCHING TO ARRAYS OF MORE THAN ONE DIMENSION
BAKER, TP
[J]. SIAM JOURNAL ON COMPUTING, 1978, 7 (04) : 533 - 541
[6] Bird R. S., 1977, Information Processing Letters, V6, P168, DOI 10.1016/0020-0190(77)90017-5
[7] FAST STRING SEARCHING ALGORITHM
BOYER, RS
MOORE, JS
[J]. COMMUNICATIONS OF THE ACM, 1977, 20 (10) : 762 - 772
[8] GONNET GH, 1988, OED8802 U WAT CTR NE
[9] GONNET GH, 1991, HDB ALGORITHMS DATA
[10] EFFICIENT RANDOMIZED PATTERN-MATCHING ALGORITHMS
KARP, RM
RABIN, MO
[J]. IBM JOURNAL OF RESEARCH AND DEVELOPMENT, 1987, 31 (02) : 249 - 260

← 1 2 →