Daniel M. Sunday
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.
- 1 Boyer, R.S., and Moore, J.S. A fast string searching algorithm. Commun. ACM 20, 10 (Oct. t977), 762-772. Google Scholar
Digital Library
- 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.Google Scholar
- 3 Knuth, D.E., Morris,J.H., and Pratt, V.R. Fast (June 1977), 323-350.Google Scholar
- 4 Smit, G.V. A comparison of three string matchin~ algorithms. Solho.--Prac. andExb. 12. I (lan. 19~32), 57-66. - " ' 'Google Scholar
Index Terms
- A very fast substring search algorithm
Recommendations
A Fast Approximate Nearest Neighbor Search Algorithm in the Hamming Space
A fast approximate nearest neighbor search algorithm for the (binary) Hamming space is proposed. The proposed Error Weighted Hashing (EWH) algorithm is up to 20 times faster than the popular locality sensitive hashing (LSH) algorithm and works well even ...
Quest for Fast Partial Search Algorithm
The Grover quantum algorithm can find a target item in a database faster than any classical algorithm. In partial search, one trades accuracy for speed, and a part of the database (a block) containing the target item can be found even faster. We ...
Reviews
Ralph Walter Wilkerson
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 the scan order of the pattern. For short pattern strings this algorithm has about a 20 percent or greater increase in search speed for normal English text. Cole presents three different variations of this algorithm with different search orderings. No complexity results are proven, though he conjectures that the worst-case behavior is O ( n ), where n is the length of the target string.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments