Article

Free access

Analysis of Boyer-Moore-type string searching algorithms

Authors:

Ricardo A. Baeza-Yates,

Gaston H. Gonnet,

Mireille RégnierAuthors Info & Claims

SODA '90: Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms

Pages 328 - 343

Published: 01 January 1990 Publication History

PDF eReader

References

[1]

K. Abrahamson. Generalized string matching. SIAM J on Computing, 16:1039-1051, 1987.

Digital Library

Google Scholar

[2]

G. Barth. An analytical comparison of two string searching algorithms. Inf. Proc. Letters, 18:249-256, 1984.

Digital Library

Google Scholar

[3]

R. Boyer and S. Moore. A fast string searching algorithm. C.A CM, 20:762-772, 1977.

Digital Library

Google Scholar

[4]

R. Baeza-Yates. Improved string searching. Software-Practice and Experience, 19(3):257-271, 1989.

Digital Library

Google Scholar

[5]

R.A. Baeza-Yates. Efficient Tex~ Searching. PhD thesis, Dept. of Computer Science, University of Waterloo, May 1989. Also as Research Report CS-89-17.

Digital Library

Google Scholar

[6]

R.A. Baeza-Yates. String searching algorithms revisited. In F. Dehne, J.-R. Sack, and N. Santoro, editors, Workshop in Algorithms and Data Slructures, pages 75-96, Ottawa, Canada, August 1989. Springer Verlag Lecture Notes on Computer Science 382.

Digital Library

Google Scholar

[7]

R. Baeza-Yates and G.H. Gonnet. A new approach to text searching. In Proc. of 1$th SIGIR, pages 168- 175, Cambridge, Mass., June 1989.

Digital Library

Google Scholar

[8]

M. Fischer and M. Paterson. String matching and other products, in R. Karp, editor, Complexity of Computation (SIAM-AMS Proceedings 7), volume 7, pages 113-125. American Mathematical Society, Providence, RI, 1974.

Google Scholar

[9]

Z. Galil. On improving the worst case running time of the Boyer-Moore string matching Mgorithm. C.A CM, 22:505-508, 1979.

Digital Library

Google Scholar

[10]

Z. GMil. Open problems in stringology. In A. Apostolico and Z. Galil, editors, Combinatorial Algorithms on Words, volume F12 of NATO ASI Series, pages 1-8. Springer-Verlag, 1985.

Google Scholar

[11]

N. Horspool. Practical fast searching in strings. Software - Practice and Experience, 10:501-506, 1980.

Google Scholar

[12]

D.E. Knuth, J. Morris, and V. Pratt. Fast pattern matching in strings. SIAM J on Computing, 6:323-350, 1977.

Google Scholar

[13]

R. Pinter. Efficient string matching with don't-care patterns. In A. Apostolico and Z. Galil, editors, Combinatorial Algorithms on Words, volume F12 of NATO ASI Series, pages 11-29. Springer-Verlag, 1985.

Google Scholar

[14]

M. Regnier. Knuth-Morris-Pratt algorithm: An analysis, in MFCS'89, Lecture Notes in Computer Science 379, pages 431-444, Porabka, Poland, August 1989. Springer-Verlag. Also as INRIA Report 966, 1989.

Digital Library

Google Scholar

[15]

R. Rivest. On the worst-case behavior of string-searching algorithms. SIAM J on Computing, 6:669-674, 1977.

Google Scholar

[16]

R. Schaback. On the expected sublinearity of the Boyer-Moore algorithm. SIAM J on Computing, 17:548- 658, 1988.

Digital Library

Google Scholar

[17]

A.C. Yao. The complexity of pattern matching for a random string. SIAM Y on Computing, 8:368-387, 1979.

Google Scholar

Cited By

View all

Marschall THerms IKaltenbach HRahmann S(2012)Probabilistic Arithmetic Automata and Their ApplicationsIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2012.1099:6(1737-1750)Online publication date: 1-Nov-2012
https://dl.acm.org/doi/10.1109/TCBB.2012.109
Sharfuddin AFeng XCunningham HRuth PKraft N(2010)Improving Boyer-Moore-Horspool using machine-words for comparisonProceedings of the 48th annual ACM Southeast Conference10.1145/1900008.1900033(1-5)Online publication date: 15-Apr-2010
https://dl.acm.org/doi/10.1145/1900008.1900033
Marschall TRahmann S(2010)Exact analysis of horspool's and sunday's pattern matching algorithms with probabilistic arithmetic automataProceedings of the 4th international conference on Language and Automata Theory and Applications10.1007/978-3-642-13089-2_37(439-450)Online publication date: 24-May-2010
https://dl.acm.org/doi/10.1007/978-3-642-13089-2_37
Show More Cited By

Index Terms

Analysis of Boyer-Moore-type string searching algorithms
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation

Recommendations

A New Proof of the Linearity of the Boyer-Moore String Searching Algorithm

The Boyer-Moore algorithm searches for all occurrences of a specified string, the pattern, in another string, the text. We study the combinatorial structure of periodic strings and use these results to derive a new proof of the linearity of the Boyer-...
Near-Optimal Quantum Algorithms for String Problems
Abstract
We study quantum algorithms for several fundamental string problems, including Longest Common Substring, Lexicographically Minimal String Rotation, and Longest Square Substring. These problems have been widely studied in the stringology literature ... $\overset{}{}^{}$ $\overset{}{}^{}$ $^{}$ $\overset{}{}^{}$ $\overset{}{} \sqrt{}$
Efficient String Matching Algorithm for Searching Large DNA and Binary Texts

The exact string matching is essential in application areas such as Bioinformatics and Intrusion Detection Systems. Speeding-up the string matching algorithm will therefore result in accelerating the searching process in DNA and binary data. Previously, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '90: Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms

January 1990

522 pages

ISBN:0898712513

Chairman:
David Johnson

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 1990

Check for updates

Qualifiers

Article

Conference

SODA90

Sponsor:

SIGACT

SODA90: ACM/SIGACT-SIAM Symposium on Discrete Algorithm

January 22 - 24, 1990

California, San Francisco, USA

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
1,717
Total Downloads

Downloads (Last 12 months)62
Downloads (Last 6 weeks)6

Reflects downloads up to 17 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Marschall THerms IKaltenbach HRahmann S(2012)Probabilistic Arithmetic Automata and Their ApplicationsIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2012.1099:6(1737-1750)Online publication date: 1-Nov-2012
https://dl.acm.org/doi/10.1109/TCBB.2012.109
Sharfuddin AFeng XCunningham HRuth PKraft N(2010)Improving Boyer-Moore-Horspool using machine-words for comparisonProceedings of the 48th annual ACM Southeast Conference10.1145/1900008.1900033(1-5)Online publication date: 15-Apr-2010
https://dl.acm.org/doi/10.1145/1900008.1900033
Marschall TRahmann S(2010)Exact analysis of horspool's and sunday's pattern matching algorithms with probabilistic arithmetic automataProceedings of the 4th international conference on Language and Automata Theory and Applications10.1007/978-3-642-13089-2_37(439-450)Online publication date: 24-May-2010
https://dl.acm.org/doi/10.1007/978-3-642-13089-2_37
Tsai T(2006)Average case analysis of the Boyer-Moore algorithmRandom Structures & Algorithms10.5555/1133618.113362228:4(481-498)Online publication date: 1-Jul-2006
https://dl.acm.org/doi/10.5555/1133618.1133622
Baker BClarkson K(1995)Parameterized pattern matching by Boyer-Moore-type algorithmsProceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/313651.313816(541-550)Online publication date: 22-Jan-1995
https://dl.acm.org/doi/10.5555/313651.313816
Cole RAggarwal A(1991)Tight bounds on the complexity of the Boyer-Moore string matching algorithmProceedings of the second annual ACM-SIAM symposium on Discrete algorithms10.5555/127787.127830(224-233)Online publication date: 1-Mar-1991
https://dl.acm.org/doi/10.5555/127787.127830

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A New Proof of the Linearity of the Boyer-Moore String Searching Algorithm

Near-Optimal Quantum Algorithms for String Problems

Efficient String Matching Algorithm for Searching Large DNA and Binary Texts