The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.7.3 String Matching

Problem Input | Problem Output

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

    Related Problems


      
    Approximate String Matching
      
    Finite State Machine Minimization
      
    Graph Isomorphism
      
    Suffix Trees and Arrays



    This page last modified on 2008-07-10 .
    www.algorist.com