2-DIMENSIONAL DICTIONARY MATCHING

被引：29

作者：

AMIR, A ^{[1
]}

FARACH, M ^{[1
]}

机构：

[1] RUTGERS STATE UNIV,DIMACS,PISCATAWAY,NJ 08855

来源：

INFORMATION PROCESSING LETTERS | 1992年 / 44卷 / 05期

基金：

美国国家科学基金会;

关键词：

ALGORITHMS; ANALYSIS OF ALGORITHMS; DICTIONARY MATCHING; PATTERN MATCHING; TEXT PROCESSING;

D O I：

10.1016/0020-0190(92)90206-B

中图分类号：

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

学科分类号：

0812 ;

摘要：

Most traditional pattern matching algorithms solve the problem of finding all occurrences of a given pattern string P in a given text T. Another important paradigm is the dictionary matching problem. Let D = {P(l),..., P(k)) be the dictionary. We seek the locations of all dictionary patterns that appear in a given text T. Previous dictionary matching algorithms have all involved exact matching of a set of strings. In this paper, we present an algorithm for the Two-Dimensional Dictionary Problem. The two-dimensional dictionary problem is that of finding each occurrence of a set of two-dimensional patterns in a text. Our algorithm runs in time O(Absolute value of D log k) preprocessing, 0(Absolute value of T log k) text processing.

引用

页码：233 / 239

页数：7

共 14 条

[1] EFFICIENT STRING MATCHING - AID TO BIBLIOGRAPHIC SEARCH [J].