Improved string matching with k mismatches

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Improved string matching with k mismatches

Full text

Pdf (176 KB)

Source

ACM SIGACT News archive
Volume 17 , Issue 4 (Spring 1986) table of contents

Pages: 52 - 54

Year of Publication: 1986

ISSN:0163-5700

Authors

Z Galil	Department of Computer Science, Tel-Aviv University and Department of Computer Science, Columbia University
R Giancarlo	Department of Computer Science, Columbia University

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	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/8307.8309 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.

	1	1. P. Weiner. Linear Pattern Matching Algorithms. Symposium on Switching and Automata Theory, IEEE, 1973, pp. 1-11.
	2	2. G.M. Landau and U. Vishkin. Efficient String Matching in the Presence of Errors. Symposium on Fundations of Computer Science, IEEE, October, 1986, pp. 126-136.
	3	G M Landau , U Vishkin, Efficient string matching with k mismatches, Theoretical Computer Science, v.43 n.2-3, p.239-249, July 1986
	4	4. G.M. Landau and U. Vishkin. Efficient String Matching with k Differences. Dept. of Computer Science, Tel-Aviv University, Tel-Aviv 69978, Israel, September, 1985.
	5	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]

CITED BY 8

	Amihood Amir , Moshe Lewenstein , Ely Porat, Faster algorithms for string matching with k mismatches, Journal of Algorithms, v.50 n.2, p.257-275, February 2004
	Richard Cole , Lee-Ad Gottlieb , Moshe Lewenstein, Dictionary matching and indexing with errors and don't cares, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Amihood Amir , Yonatan Aumann , Gary Benson , Avivit Levy , Ohad Lipsky , Ely Porat , Steven Skiena , Uzi Vishne, Pattern matching with address errors: rearrangement distances, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1221-1229, January 22-26, 2006, Miami, Florida
	Ricardo Baeza-Yates , Gaston H. Gonnet, A new approach to text searching, Communications of the ACM, v.35 n.10, p.74-82, Oct. 1992
	Prahlad Fogla , Wenke Lee, q-Gram Matching Using Tree Models, IEEE Transactions on Knowledge and Data Engineering, v.18 n.4, p.433-447, April 2006
	Carmit Hazay , Moshe Lewenstein , Dina Sokol, Approximate parameterized matching, ACM Transactions on Algorithms (TALG), v.3 n.3, p.29-es, August 2007
	Szymon Grabowski , Kimmo Fredriksson, Bit-parallel string matching under Hamming distance in O(n⌈m/w⌉) worst case time, Information Processing Letters, v.105 n.5, p.182-187, February, 2008
	Amihood Amir , Yonatan Aumann , Gary Benson , Avivit Levy , Ohad Lipsky , Ely Porat , Steven Skiena , Uzi Vishne, Pattern matching with address errors: Rearrangement distances, Journal of Computer and System Sciences, v.75 n.6, p.359-370, September, 2009