Practical fast searching in strings

1980/06/01 by R. Nigel Horspool · 601 citations
Computer Science · #Algorithm #Algorithms and Data Compression #Computer science #Data structure #Natural Language Processing Techniques #Programming language #Substring #Theoretical computer science #semigroups and automata theory

paper · doi:10.1002/spe.4380100608

published in Software Practice and Experience 10(6), 501-506 (Wiley)

openalex publication_date 1980/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/25

Abstract

Abstract The problem of searching through text to find a specified substring is considered in a practical setting. It is discovered that a method developed by Boyer and Moore can outperform even special‐purpose search instructions that may be built into the computer hardware. For very short substrings however, these special purpose instructions are fastest—provided that they are used in an optimal way.

Citations

• Fast Pattern Matching in Strings

Cited by

• Monotonic run length text sampling and fake sampled positions
• Probabilistic Arithmetic Automata and their Applications
• Regular Expression Indexing for Log Analysis. Extended Version
• Representing Pattern Matching Algorithms by Polynomial-Size Automata
• LZgrep: a Boyer-Moore string matching tool for Ziv-Lempel compressed text
• The Exact String Matching Problem: a Comprehensive Experimental Evaluation
• Flexible and Efficient Algorithms for Abelian Matching in Strings
• A guided tour to approximate string matching
• A Fast Generic Sequence Matching Algorithm
• NR‐grep: a fast and flexible pattern‐matching tool
• Exact Online String Matching Bibliography
• Detecting k-(Sub-)Cadences and Equidistant Subsequence Occurrences
• Fast algorithms for single and multiple pattern Cartesian tree matching
• Using an ensemble of statistical metrics to quantify large sets of plant transcription factor binding sites. [europepmc]
• Entropy-Based Approach in Selection Exact String-Matching Algorithms. [europepmc]
• PEPMatch: a tool to identify short peptide sequence matches in large sets of proteins. [europepmc]
• Direct construction of sparse suffix arrays with Libsais. [europepmc]

Related

• A new problem in string searching
• Technology Beats Algorithms (in Exact String Matching)
• Fast Packed String Matching for Short Patterns
• Fast Searching in Packed Strings
• Suffix Arrays: A New Method for On-Line String Searches