main page  —  COMP 526 Applied Algorithmics

Unit 4: String Matching – What’s behind Ctrl+F?

This unit covers algorithms for exact string matching:

  • terminology for strings
  • string matching with determinstic finite automata
  • Knuth-Morris-Pratt (KMP) algorithm
  • Boyer-Moore (BM) algorithm
  • Rabin-Karp (RK) algorithm

Learning outcomes

  1. Know and use typical notions for strings (substring, prefix, suffix, etc.).
  2. Understand principles and implementation of the KMP, BM, and RK algorithms.
  3. Know the performance characteristics of the KMP, BM, and RK algorithms.
  4. Be able to solve simple stringology problems using the KMP failure function.

Material


Further reading and sources

The naive string matching algorithm, string matching with automata and the Knuth-Morris-Pratt are discussed, e.g., in

The description of the Boyer-Moore algorithm follows our own algorithms textbook (in German):

The presentation of Rabin-Karp and the failure-link automaton is inspired by material prepared for the module


Unit 3  ⋅  Syllabus  ⋅  Unit 5