A very fast substring search algorithm

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A very fast substring search algorithm

Full text

Pdf (1.03 MB)

Source

Communications of the ACM archive
Volume 33 , Issue 8 (August 1990) table of contents

Pages: 132 - 142

Year of Publication: 1990

ISSN:0001-0782

Author

Daniel M. Sunday

East Stroudsburg Univ. of Pennsylvania, East Stroudsburg, PA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 44, Downloads (12 Months): 378, Citation Count: 27

Additional Information:

abstract 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/79173.79184 What is a DOI?

ABSTRACT

This article describes a substring search algorithm that is faster than the Boyer-Moore algorithm. This algorithm does not depend on scanning the pattern string in any particular order. Three variations of the algorithm are given that use three different pattern scan orders. These include: (1) a “Quick Search” algorithm; (2) a “Maximal Shift” and (3) an “Optimal Mismatch” algorithm.

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	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]
	2	Guibas, L..j., and Odiyzko, A.M. A new proof of the linearity of the Boyer-Moore String Searching Algorithm. SIAM J. Comput. 9, 4 (No,:. !980), 672-682.
	3	Knuth, D.E., Morris,J.H., and Pratt, V.R. Fast (June 1977), 323-350.
	4	Smit, G.V. A comparison of three string matchin~ algorithms. Solho.--Prac. andExb. 12. I (lan. 19~32), 57-66. - " ' '

CITED BY 28

	Wilfred J. Hansen, Subsequence references: first-class values for substrings, ACM Transactions on Programming Languages and Systems (TOPLAS), v.14 n.4, p.471-489, Oct. 1992
	Diane Crawford, Technical correspondence, Communications of the ACM, v.35 n.4, p.132, April 1992
	Han Kesong , Wang Yongcheng , Chen Guilin, Research on a faster algorithm for pattern matching, Proceedings of the fifth international workshop on on Information retrieval with Asian languages, p.119-124, September 30-October 01, 2000, Hong Kong, China
	Ricardo Baeza-Yates , Gonzalo Navarro, Block addressing indices for approximate text retrieval, Proceedings of the sixth international conference on Information and knowledge management, p.1-8, November 10-14, 1997, Las Vegas, Nevada, United States
	Gonzalo Navarro, A guided tour to approximate string matching, ACM Computing Surveys (CSUR), v.33 n.1, p.31-88, March 2001
	Edleno Silva de Moura , Gonzalo Navarro , Nivio Ziviani , Ricardo Baeza-Yates, Fast searching on compressed text allowing errors, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.298-306, August 24-28, 1998, Melbourne, Australia
	Arthur Gittleman, Predicting string search speed, Journal of Experimental Algorithmics (JEA), 1, p.2-es, 1996
	Edleno Silva de Moura , Gonzalo Navarro , Nivio Ziviani , Ricardo Baeza-Yates, Fast and flexible word searching on compressed text, ACM Transactions on Information Systems (TOIS), v.18 n.2, p.113-139, April 2000
	Brenda S. Baker, Parameterized pattern matching by Boyer-Moore-type algorithms, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.541-550, January 22-24, 1995, San Francisco, California, United States
	Ricardo Baeza-Yates , Gonzalo Navarro, New and faster filters for multiple approximate string matching, Random Structures & Algorithms, v.20 n.1, p.23-49, January 2002
	Torben Amtoft , Charles Consel , Olivier Danvy , Karoline Malmkjær, The abstraction and instantiation of string-matching programs, The essence of computation: complexity, analysis, transformation, Springer-Verlag New York, Inc., New York, NY, 2002
	Maxime Crochemore , Costas S. Iliopoulos , Thierry Lecroq , Yoan J. Pinzon , Wojciech Plandowski , Wojciech Rytter, Occurrence and substring heuristics for δ-matching, Fundamenta Informaticae, v.56 n.1,2, p.1-21, July 2003
	Sun Kim, A new string-pattern matching algorithm using partitioning and hashing efficiently, Journal of Experimental Algorithmics (JEA), 4, p.2-es, 1999
	Tun-Wen Pai , Margaret Dah-Tsyr Chang , Jia-Han Chu , Wei-Yuan Chang , Hsiu Ling Tai, Ladderlike stepping and interval jumping searching algorithms for DNA sequences, Proceedings of the second conference on Asia-Pacific bioinformatics, p.93-98, January 01, 2004, Dunedin, New Zealand
	Gonzalo Navarro , Mathieu Raffinot, Fast and flexible string matching by combining bit-parallelism and suffix automata, Journal of Experimental Algorithmics (JEA), 5, p.4-es, 2000
	Maxime Crochemore , Christophe Hancart , Thierry Lecroq, A unifying look at the Apostolico--Giancarlo string-matching algorithm, Journal of Discrete Algorithms, v.1 n.1, p.37-52, February 2003
	Paolo Boldi , Sebastiano Vigna, Mutable strings in Java: design, implementation and lightweight text-search algorithms, Science of Computer Programming, v.54 n.1, p.3-23, January 2005
	Gonzalo Navarro , Jorma Tarhio, LZgrep: a Boyer–Moore string matching tool for Ziv–Lempel compressed text: Research Articles, Software—Practice & Experience, v.35 n.12, p.1107-1130, October 2005
	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
	Markus E. Nebel, Fast string matching by using probabilities: on an optimal mismatch variant of Horspool's algorithm, Theoretical Computer Science, v.359 n.1, p.329-343, 14 August 2006
	Longtao He , Binxing Fang , Jie Sui, The wide window string matching algorithm, Theoretical Computer Science, v.332 n.1-3, p.391-404, 28 February 2005
	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
	Frantisek Franek , Christopher G. Jennings , W. F. Smyth, A simple fast hybrid pattern-matching algorithm, Journal of Discrete Algorithms, v.5 n.4, p.682-695, December, 2007
	Jan Holub , W. F. Smyth , Shu Wang, Fast pattern-matching on indeterminate strings, Journal of Discrete Algorithms, v.6 n.1, p.37-50, March, 2008
	Kimmo Fredriksson, Succinct backward-DAWG-matching, Journal of Experimental Algorithmics (JEA), 13, February 2009
	Liuling Dai, An aggressive algorithm for multiple string matching, Information Processing Letters, v.109 n.11, p.553-559, May, 2009
	Kimmo Fredriksson , Fedor Nikitin, Simple Random Access Compression, Fundamenta Informaticae, v.92 n.1-2, p.63-81, January 2009
	Sergio Deusdado , Paulo Carvalho, GRASPm: an efficient algorithm for exact pattern-matching in genomic sequences, International Journal of Bioinformatics Research and Applications, v.5 n.4, p.385-401, July 2009

INDEX TERMS

Primary Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2 Nonnumerical Algorithms and Problems
Subjects: Pattern matching

General Terms:
Algorithms, Theory

REVIEW

"Ralph Walter Wilkerson : Reviewer"

The substring search algorithm described in this paper is an extension of the well-known Boyer-Moore algorithm. Unlike the Boyer-Moore algorithm, which requires scanning the pattern string in reverse order, this algorithm is not dependent on t more...

Collaborative Colleagues:

Daniel M. Sunday: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player