Alphabet independent two dimensional matching

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Alphabet independent two dimensional matching

Full text

Pdf (844 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fourth annual ACM symposium on Theory of computing table of contents

Victoria, British Columbia, Canada

Pages: 59 - 68

Year of Publication: 1992

ISBN:0-89791-511-9

Authors

Amihood Amir	College of Computing, Georgia Institute of Technology, Atlanta, GA
Gary Benson	Dept. of Computer Science, University of Maryland, College Park, MD
Martin Farach	DIMACS, Box 1179, Rutgers University, Piscataway, NJ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 24, Citation Count: 11

Additional Information:

references cited by index terms review 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/129712.129719 What is a DOI?

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.

	AB92	Amihood Amir , Gary Benson, Two-dimensional periodicity and its applications, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.440-452, September 1992, Orlando, Florida, United States
	AC75	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]
	AF91	A. Amir and M. Farach. Two dimensional dictionary matching. Manuscript, 1991.
	AL91	Amihood Amir , Gad M. Landau, Fast parallel and serial multidimensional approximate array matching, Theoretical Computer Science, v.81 n.1, p.97-115, April 22, 1991 [doi>10.1016/0304-3975(91)90318-V]
	ALV90	Amihood Amir , Gad M. Landau , Usi Vishkin, Efficient pattern matching with scaling, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.344-357, January 22-24, 1990, San Francisco, California, United States
	Bak78	T.J. Baker. A technique for extending rapid exact-match string matching to arrays of more than one dimension. SIAM J. Corny, 7:533-541, 1978.
	Bir77	R.S. Bird. Two dimensional pattern matching. Information Processing Letters, 6(5):168-170, 1977.
	BM77	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]
	CS85	M.T. Chen and J. Seiferas. Efficient and elegant subword tree construction. In A. Apostolico and Z. Galil, editors, Combinatorial Algorithms on Words, chapter 12, pages 97-107. NATO ASI Series F: Computer and System Sciences, 1985.
	FP74	M.J. Fischer and M.S. Paterson. String matching and other products. Complezfly of Computation, R.M. Karp (editor), SIAM-AMS Proceedings, 7:113-125, 1974.
	Gal85	Z. Galil. Open problems in stringology. In Z. Galil A. Apostolico, editor, Combinatorial Algorithms on Words, volume 12, pages 1-8. NATO ASI Series F, 1985.
	GS83	Z. Galil and J.I. Seiferas. Time-spaceoptimal string matching. J. Computer and System Science, 26:280-294, 1983.
	HT84	Dov Harel , Robert Endre Tarjan, Fast algorithms for finding nearest common ancestors, SIAM Journal on Computing, v.13 n.2, p.338-355, May 1984 [doi>10.1137/0213024]
	KMP77	D.E. Knuth, J.H. Morris, and V.R. Pratt. Fast pattern matching in strings. SIAM J. Comp., 6:323-350, 1977.
	KMR72	Richard M. Karp , Raymond E. Miller , Arnold L. Rosenberg, Rapid identification of repeated patterns in strings, trees and arrays, Proceedings of the fourth annual ACM symposium on Theory of computing, p.125-136, May 01-03, 1972, Denver, Colorado, United States [doi>10.1145/800152.804905]
	KR87	Richard M. Karp , Michael O. Rabin, Efficient randomized pattern-matching algorithms, IBM Journal of Research and Development, v.31 n.2, p.249-260, March 1987
	LV85	G.M. Landau and U. Vishkin. Efficient string matching in the presence of errors. Proc. #Oth IEEE FOCS, pages 126-126, 1985.
	McC76	Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976 [doi>10.1145/321941.321946]
	ML84	Michael G. Main , Richard J. Lorentz, An O(n log n) algorithm for finding all repetitions in a string, Journal of Algorithms, v.5 n.3, p.422-432, Sept. 1984 [doi>10.1016/0196-6774(84)90021-X]
	RK82	Azriel Rosenfeld , Avinash C. Kak, Digital Picture Processing, Academic Press, Inc., Orlando, FL, 1982
	Vis91	Uzi Vishkin, Deterministic sampling: a new technique for fast pattern matching, SIAM Journal on Computing, v.20 n.1, p.22-40, Feb. 1991 [doi>10.1137/0220002]
	Wei73	P. Weiner. Linear pattern matching algorithm. Proc. 1# IEEE Symposium on Switching and Automata Theory, pages 1- 11, 1973.

CITED BY 11

	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
	Amihood Amir , Gary Benson , Martin Farach, Optimal parallel two dimensional pattern matching, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.79-85, June 30-July 02, 1993, Velen, Germany
	S. Muthukrishnan , Krishna Palem, Non-standard stringology: algorithms and complexity, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.770-779, May 23-25, 1994, Montreal, Quebec, Canada
	Amihood Amir , Martin Farach , Ramana M. Idury , Johannes A. La Poutré , Alejandro A. Schäffer, Improved dynamic dictionary matching, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.392-401, January 25-27, 1993, Austin, Texas, United States
	Rafaele Giancarlo, The Suffix of a square matrix, with applications, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.402-411, January 25-27, 1993, Austin, Texas, United States
	Filippo Mignosi , Antonio Restivo , Pedro V. Silva, On Fine and Wilf's theorem for bidimensional words, Theoretical Computer Science, v.292 n.1, p.245-262, January 2003
	Chiara Epifanio , Michel Koskas , Filippo Mignosi, On a conjecture on bidimensional words, Theoretical Computer Science, v.299 n.1-3, p.123-150, 18 April 2003
	Chiara Epifanio , Filippo Mignosi, A multidimensional critical factorization theorem, Theoretical Computer Science, v.346 n.2, p.265-280, 28 November 2005
	Amihood Amir , Oren Kapah , Dekel Tsur, Faster two-dimensional pattern matching with rotations, Theoretical Computer Science, v.368 n.3, p.196-204, December, 2006
	Shmuel T. Klein , Riva Shalom , Yair Kaufman, Searching for a set of correlated patterns, Journal of Discrete Algorithms, v.5 n.1, p.149-161, March, 2007