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.

Implementations

  • Fire-Engine and Spare-Parts String and Language Algorithms (C++) (rating 7)
  • David Eppstein's Knuth-Morris-Pratt Algorithm and Minkowski sum code (C++) (rating 4)
  • Handbook of Algorithms and Data Structures (Pascal) (rating 4)
  • Algorithms in C++ -- Sedgewick (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

    Go to the corresponding chapter in the book
    About the Book
    Send us Mail
    Go to Main Page

    This page last modified on Tue Jun 03, 1997 .