A very fast substring search algorithm
Communications of the ACMPublished 1 August 1990Open access
Daniel M. Sunday
Citations390
SJR quartileQ1
SJR score1.15
SNIP3.34
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
A substring search algorithm that is faster than the Boyer-Moore algorithm and does not depend on scanning the pattern string in any particular order is described.
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.
Keywords
Computer ScienceBiochemistry, Genetics and Molecular Biology
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 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.