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 [J].
AHO, AV ;
CORASICK, MJ .
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 [J].
BAKER, TP .
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 [J].
BOYER, RS ;
MOORE, JS .
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 [J].
KARP, RM ;
RABIN, MO .
IBM JOURNAL OF RESEARCH AND DEVELOPMENT, 1987, 31 (02) :249-260
12