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

This is an archived version of this module from Spring 2021.
Click here for the current iteration.

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
• lecture notes

• tutorial problems

• Video 4-1 (2021-03-03, 14:57): §4.1 Introduction
  
  Chapters

  1:57 Applications and context
  4:20 Formal notation
  10:49 Problem definition
  
• Video 4-2 (2021-03-09, 12:32): §4.2 Brute force string matching
  
  Chapters

  0:15 Guesses and checks
  2:08 Observations
  4:35 Brute force
  
• Video 4-3 (2021-03-09, 15:26): §4.3 String matching with finite automata
  
  Chapters

  0:18 Theoretical background poll
  2:37 String matching with DFA
  5:08 Practical challenges
  6:04 Simulating the automaton
  9:57 Intuition and invariant
  
• Video 4-4 (2021-03-09, 23:12): §4.3 Constructing string matching DFAs
  
  Chapters

  0:31 Introduction to NFAs
  1:04 Simulating the NFA
  2:04 State set simulation
  3:56 NFA to DFA conversion
  4:46 Inductive construction
  7:19 Transition function logic
  11:24 Constructing new edges
  14:06 KMP DFA construction
  19:37 Algorithm efficiency
  20:32 KMP performance review
  
• Video 4-5 (2021-03-09, 25:01): §4.4 The Knuth-Morris-Pratt algorithm
  
  Chapters

  0:20 Failurelinks
  3:50 Automata
  6:30 Algorithm
  11:50 Failure links
  18:55 Prefix function
  
• Video 4-6 (2021-03-10, 31:01): §4.5 The Boyer-Moore algorithm
  
  Chapters

  0:30 Motivation
  9:34 Boyer-Moore Algorithm - Code
  11:02 Bad character examples
  13:31 Last-Occurrence Function
  16:55 Good suffix examples
  21:13 Good suffix jumps
  24:31 Boyer-Moore algorithm - Discussion
  
• Video 4-7 (2021-03-10, 20:18): §4.6 The Rabin-Karp algorithm
  
  Chapters

  8:00 Rolling hashes
  14:50 Another question
  15:05 A test
  16:45 Problems
  

---

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 my 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 3  ⋅  Syllabus  ⋅  Unit 5