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.

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 .