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.
The best book available for this problem is
Algorithms on Strings, Trees, and Sequences
by
Dan Gusfield.
Implementations
Fire-Engine and Spare-Parts String and Language Algorithms (C++) (rating 7)
Algorithms in C++ -- Sedgewick (C++) (rating 4)
Handbook of Algorithms and Data Structures (Pascal) (rating 4)
BIPM -- Bipartite Matching Codes (C++) (rating 4)
Xtango and Polka Algorithm Animation Systems (C++) (rating 3)
Related Problems
Approximate String Matching
Finite State Machine Minimization
Graph Isomorphism
Suffix Trees and Arrays
Previous Problem
Next Problem
View the graph for this
file
Bulletin Board
About ``The Algorithm Design Manual''.
Send us Mail
The Stony Brook Algorithm Repository -- go to front page
This page last modified on Wed Mar 07, 2001
.