string-search algorithm has been the standard benchmark for the practical string-search literature. Algorithms using a finite set of patterns In the following compilation, M is the length of the longest pattern, m their total length, n the length of the searchable text, o the number of occurrences. Algorithms using an infinite number of patterns Naturally, the patterns can not be enumerated finitely in this case. They are represented usually by a regular grammar or regular expression. Classification by the use of preprocessing programs Other classification approaches are possible. One of the most common uses preprocessing as main criteria. Classification by matching strategies Another one classifies the algorithms by their matching strategy: Match the prefix first (Knuth–Morris–Pratt, Shift-And, Aho–Corasick) Match the suffix first (Boyer–Moore and variants, Commentz-Walter) Match the best factor first (BNDM, BOM, Set-BOM) Other strategy (Naïve, Rabin–Karp) See also Sequence alignment Graph matching Pattern matching Compressed pattern matching Matching wildcards Full-text search References R. S. Boyer and J. S. Moore, A fast string searching algorithm, Carom. ACM 20, (10), 262–272(1977). Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. MIT Press and McGraw-Hill, 2009. . Chapter 32: String Matching, pp. 985–1013. External links Huge list of pattern matching links Last updated: 12/27/2008 20:18:38 Large (maintained) list of string-matching algorithms NIST list of string-matching algorithms StringSearch – high-performance pattern matching algorithms in Java – Implementations of many String-Matching-Algorithms in Java (BNDM, Boyer-Moore-Horspool, Boyer-Moore-Horspool-Raita, Shift-Or) StringsAndChars – Implementations of many String-Matching-Algorithms (for single and multiple patterns) in Java Exact String Matching Algorithms — Animation in Java, Detailed description and C implementation of many algorithms. (PDF) Improved Single and Multiple Approximate String Matching Kalign2: high-performance multiple alignment of protein and nucleotide sequences allowing external features NyoTengu – high-performance pattern matching algorithm in C – Implementations of Vector and Scalar String-Matching-Algorithms in C