Module: String matching

Naive (brute force) string matching, matching with finite state automata, Knuth-Morris-Pratt algorithm, Rabin-Karp algorithm

Learning Outcomes

Understand string matching

Understand when, why, and how to use string matching.

Readings

CLRS 32 - String matching

The naive string matching algorithm, the Robin-Karp algorithm, string matching with finite automata, the Knuth-Morris-Pratt algorithm

Textbook 29 pages

Notes on string matching

Naive (brute force) string matching, matching with finite state automata, Knuth-Morris-Pratt algorithm, Rabin-Karp algorithm

Notes