The Boyer–Moore–Galil String Searching Strategies Revisited
SIAM Journal on ComputingPublished 1 February 1986
Alberto Apostolico, Raffaele Giancarlo
Citations141
SJR quartileQ1
SJR score1.40
SNIP1.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Based on the Boyer–Moore–Galil approach, a new algorithm is proposed which requires a number of character comparisons bounded by 2n, regardless of the number of occurrences of the pattern in the textstring.
Abstract
Based on the Boyer–Moore–Galil approach, a new algorithm is proposed which requires a number of character comparisons bounded by 2n, regardless of the number of occurrences of the pattern in the textstring. Preprocessing is only slightly more involved and still requires a time linear in the pattern size.
Keywords
Computer Science
Communications of the ACMEfficient string matching
2,946 Citations1975Alfred V. Aho, Margaret J. Corasick
A simple, efficient algorithm to locate all occurrences of any of a finite number of keywords in a string of text that has been used to improve the speed of a library bibliographic search program by a factor of 5 to 10.
SIAM Journal on ComputingFast Pattern Matching in Strings
2,917 Citations1977Donald E. Knuth, James H. Morris +1 more
An algorithm is presented which finds all occurrences of one given string within another, in running time proportional to the sum of the lengths of the strings, showing that the set of concatenations of even palindromes, i.e., the language $\{\alpha \alpha ^R\}^*$, can be recognized in linear time.
Communications of the ACMA fast string searching algorithm
2,292 Citations1977Robert S. Boyer, J Strother Moore
The algorithm has the unusual property that, in most cases, not all of the first i.” in another string, are inspected.
SIAM Journal on ComputingThe Complexity of Pattern Matching for a Random String
159 Citations1979Andrew Chi-Chih Yao
It is proved that, for large m, almost all patterns $\alpha$ of length m satisfy c($\alpha), which confirms a conjecture raised in a recent paper by Knuth, Morris, and Pratt [1977].
Communications of the ACMOn improving the worst case running time of the Boyer-Moore string matching algorithm
105 Citations1979Zvi Galil
It is shown how to modify the Boyer-Moore string matching algorithm so that its worst case running time is linear even when multiple occurrences of the pattern are present in the text.
SIAM Journal on ComputingA Correct Preprocessing Algorithm for Boyer–Moore String-Searching
62 Citations1980Wojciech Rytter
The correction to Knuth’s algorithm for computing the table of pattern shifts later used in the Boyer–Moore algorithm for pattern matching is presented.
SIAM Journal on ComputingA New Proof of the Linearity of the Boyer-Moore String Searching Algorithm
54 Citations1980Leo J. Guibas, Andrew Odlyzko
The combinatorial structure of periodic strings is studied and a new proof of the linearity of the Boyer-Moore algorithm in the worst case is derived, reducing the previously best known bound of $7n$ to $4n$, where n is the length of the text.