A technique for two-dimensional pattern matching

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A technique for two-dimensional pattern matching

Full text

Pdf (880 KB)

Source

Communications of the ACM archive
Volume 32 , Issue 9 (September 1989) table of contents
Special issue: multiprocessing

Pages: 1110 - 1120

Year of Publication: 1989

ISSN:0001-0782

Authors

Rui Feng Zhu	Univ. of Ibaraki, Hitachi, Japan
Tadao Takaoka	Univ. of Ibaraki, Hitachi, Japan

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 42, Citation Count: 8

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/66451.66459 What is a DOI?

ABSTRACT

By reducing an array matching problem to a string matching problem in a natural way, it is shown that efficient string matching algorithms can be applied to arrays, assuming that a linear preprocessing is made on the text.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , Margaret J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM, v.18 n.6, p.333-340, June 1975 [doi>10.1145/360825.360855]
	2	Alberto Apostolico , Raffaele Giancarlo, The Boyer Moore Galil string searching strategies revisited, SIAM Journal on Computing, v.15 n.1, p.98-105, Feb. 1986 [doi>10.1137/0215007]
	3	Baker, T.P. A technique for extending rapid exact-match string matching to arrays of more than one dimension. SIAM J. Comput. 7, ,3 (Nov. 1978), 533-541.
	4	Bird, R.S. Two dimensional pattern matching. Info. Process. Lett. 6, 5 (Oct. 1977), 168-170.
	5	Robert S. Boyer , J. Strother Moore, A fast string searching algorithm, Communications of the ACM, v.20 n.10, p.762-772, Oct. 1977 [doi>10.1145/359842.359859]
	6	G Davies , S Bowsher, Algorithms for pattern matching, Software—Practice & Experience, v.16 n.6, p.575-601, June. 1986 [doi>10.1002/spe.4380160608]
	7	Zvi Galil, On improving the worst case running time of the Boyer-Moore string matching algorithm, Communications of the ACM, v.22 n.9, p.505-508, Sept. 1979 [doi>10.1145/359146.359148]
	8	Knuth, D.E., Morris, J.H., and Pratt, V.R. Fast pattern matching in ,,;trings. SIAM }. Comput. 6, 2 (June 1977), 323-350.
	9	Zhu Rui Feng , T. Takaoka, On improving the average case of the Boyer-Moore string matching algorithm, Journal of Information Processing, v.10 n.3, p.173-177, 1987

CITED BY 8

	Jang-Jongm Fanm , Keh-Yih Su, The Design of Efficient Algorithms for Two-Dimensional Pattern Matching, IEEE Transactions on Knowledge and Data Engineering, v.7 n.2, p.318-327, April 1995
	Juha Kärkkäinen , Esko Ukkonen, Two and higher dimensional pattern matching in optimal expected time, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.715-723, January 23-25, 1994, Arlington, Virginia, United States
	Ramana M. Idury , Alejandro A. Schäffer, Multiple matching of rectangular patterns, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.81-90, May 16-18, 1993, San Diego, California, United States
	Alok Choudhary , Sanjay Ranka, Mesh and pyramid algorithms for iconic indexing, Proceedings of the 5th international conference on Supercomputing, p.295-303, June 17-21, 1991, Cologne, West Germany
	C. C. Liu , A. L. P. Chen, 3D-List: A Data Structure for Efficient Video Query Processing, IEEE Transactions on Knowledge and Data Engineering, v.14 n.1, p.106-122, January 2002
	Leena Salmela , Jorma Tarhio , Jari Kytöjoki, Multipattern string matching with q-grams, Journal of Experimental Algorithmics (JEA), 11, 2006
	H. Yao , S. Sinha , C. Chiang , X. Hong , Y. Cai, Efficient process-hotspot detection using range pattern matching, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
	Jingyu Xu , Subarna Sinha , Charles C. Chiang, Accurate detection for process-hotspots with vias and incomplete specification, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California