Unit 6: 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

• slides (preliminary)

---

Further reading and sources

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

• Sedgewick, Wayne: Algorithms 4th ed (2011), Pearson
• Algorithms 4th ed booksite

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

• Nebel, Wild: Entwurf und Analyse von Algorithmen (2018), Springer Vieweg

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

• Data Structuring and Data Management, University of Waterloo

---

Unit 5  ⋅  Syllabus  ⋅  Unit 7