Sebastian Wild Algorithms Group · Universität Marburg

main page  —  COMP 526 Efficient Algorithms

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

This is an archived version of this module from Fall 2022.
 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

  • Video 4-1 · transcript (2022-10-26, 19:49): §4.1 Introduction
    Chapters0:39 Learning Outcomes
    1:51 Outline
    2:02 Ubiquitous strings
    5:09 Notations
    13:24 String matching-Definition
    17:02 Clicker Question
  • Video 4-2 · transcript (2022-10-26, 9:53): §4.2 Brute force string matching
    Chapters1:44 Measuring algorithm cost
    2:42 Example of brute force
    5:33 Performance and worst cases
    7:22 Improving search efficiency
  • Video 4-3 · transcript (2022-10-26, 19:06): §4.3 String matching with finite automata
    Chapters1:54 Language theory context
    6:20 Automaton mechanics
    10:37 State transitions logic
  • Video 4-4 · transcript (2022-10-26, 29:17): §4.4 Constructing string matching DFAs
  • Video 4-5 · transcript (2022-10-26, 13:28): §4.5 The Knuth-Morris-Pratt algorithm
    Chapters0:40 Failure Links
    3:28 Failure link automaton - Example
    7:31 Clicker Question
    10:47 The Knuth-Morris-Pratt Algorithm
  • Video 4-6 · transcript (2022-10-31, 15:16): §4.5 The Knuth-Morris-Pratt algorithm - analyssis
    Chapters2:18 Computing failure links
    6:52 Knuth-Morris-Pratt - Discussion
    10:55 Clicker Question
    13:01 The KMP prefix function
  • Video 4-7 · transcript (2022-10-31, 26:29): §4.6 The Boyer-Moore algorithm
    Chapters0:20 Motivation
    8:42 Boyer-Moore Algorithm - Code
    10:03 Bad character examples
    11:46 Last-Occurrence Function
    14:44 Good suffix examples
    17:32 Good suffix jumps
    20:52 Boyer-Moore algorithm - Discussion
    23:28 Clicker Question
  • Video 4-8 · transcript (2022-10-31, 11:11): §4.7 The Rabin-Karp algorithm
    Chapters0:47 Rabin-Karp Fingerprint Algorithm - Idea
    3:06 Rabin-Karp Fingerprint Algorithm - First Attempt
    4:36 Rabin-Karp Fingerprint Algorithm - Fast Rehash
    6:03 Rabin-Karp Fingerprint Algorithm - Code
    7:59 Clicker Question

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