About the Book

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.7.3 String Matching

INPUT                    OUTPUT

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.

Implementations

GNU grep (C) (rating 10)

Strmat: collection of C programs implementing exact pattern matching algorithms (C) (rating 9)

Fire-Engine and Spare-Parts String and Language Algorithms (C++,C) (rating 8)

Boost: C++ Libraries (C++) (rating 7)

Algorithms in C++ -- Sedgewick (C++) (rating 3)

Handbook of Algorithms and Data Structures (C,Pascal) (rating 3)

Recommended Books

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	Graph Isomorphism
Suffix Trees and Arrays

The Stony Brook Algorithm Repository

1.7.3 String Matching

INPUT OUTPUT

Implementations

Recommended Books

Related Problems