Journal of Chemical Information and Computer Sciences · 2004 · 55 citations · 8 references
ComputingComputer ScienceAlgorithmsData StructuresSequence AnalysisPattern RecognitionSearching AlgorithmsString AlgorithmsPattern MatchingPattern Matching AlgorithmsString Search
The advent of digital computers has made the routine use of pattern-matching possible in various applications. This has also stimulated the development of many algorithms. In this paper, we propose a new algorithm that offers improved performance compared to those reported in the literature so far. The new algorithm has been evolved after analyzing the well-known algorithms such as Boyer-Moore, Quick-search, Raita, and Horspool. The overall performance of the proposed algorithm has been improved using the shift provided by the Quick-search bad-character and by defining a fixed order of comparison. These result in the reduction of the character comparison effort at each attempt. The best- and the worst- case time complexities are also presented in this paper. Most importantly, the proposed method has been compared with the other widely used algorithms. It is interesting to note that the new algorithm works consistently better for any alphabet size.
8
A fast string searching algorithm
Robert S. Boyer, J Strother Moore · Communications of the ACM · 1977 · 2.3K citations · Full text
Practical fast searching in strings
R. Nigel Horspool · Software Practice and Experience · 1980 · 600 citations
A very fast substring search algorithm
Daniel M. Sunday · Communications of the ACM · 1990 · 390 citations · Full text
The object-oriented systems life cycle
Brian Henderson‐Sellers, Julian M. Edwards · Communications of the ACM · 1990 · 293 citations · Full text
Computing, Computer Science, Design +17
TROLL—Tandem Repeat Occurrence Locator
Adalberto T. Castelo, Wellington S. Martins, Guang R. Gao · Bioinformatics · 2002 · 213 citations · Full text