Input Description: A text string t of length n. A patterns string p of length m.
Problem: Find the first (or all) instances of the pattern in the text.
Excerpt from The Algorithm Design Manual: String matching is fundamental to database and text processing applications. Every text editor must contain a mechanism to search the current document for arbitrary strings. Pattern matching programming languages such as Perl and Awk derive much of their power from their built-in string matching primitives, making it easy to fashion programs that filter and modify text. Spelling checkers scan an input text for words in the dictionary and reject any strings that do not match.
|GNU grep (rating 10)
|Strmat (rating 9)
|fuzzywuzzy (rating 8)
|Fire-Engine and Spare-Parts String and Language Algorithms (rating 8)
|amatch (rating 7)
|aho-corasick (rating 7)
|ahocorasick (rating 7)
|C++ Boost Library (rating 7)
|Algorithms in C++ (rating 3)
|Handbook of Algorithms and Data Structures (rating 3)
|Algorithms in Java, Third Edition (Parts 1-4) by Robert Sedgewick and Michael Schidlowsky
|Algorithms on Strings, Trees, and Sequences by Dan Gusfield
|Practical Algorithms for Programmers by A. Binstock and J. Rex
|String Searching Algorithms by G. A. Stephen
|Text Algorithms by M. Crochemore and W. Rytter
|Handbook of Algorithms and Data Structures by G. Gonnet and R. Baeza-Yates
|Introduction to Algorithms by T. Cormen and C. Leiserson and R. Rivest and C. Stein
|Introduction to Algorithms by U. Manber
|Computer Algorithms by S. Baase
Approximate String Matching
Finite State Machine Minimization
Suffix Trees and Arrays
As an Amazon affiliate, I earn from qualifying purchases if you buy from links on this website.