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 Spring 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 (2022-02-28, 18:56): §4.1 Introduction
    Chapters0:45 Learning Outcomes
    2:47 Ubiquitous strings
    5:49 Notations
    12:31 Clicker Question
    13:08 String matching - Definition
  • Video 4-2 (2022-02-28, 9:49): §4.2 Brute force string matching
    Chapters0:08 The Brute Force Method
    3:38 Brute Force Method
    9:13 Inverted Indices
  • Video 4-3 (2022-02-28, 13:47): §4.3 String matching with finite automata
    Chapters3:23 Theory
    8:29 Explanation
  • Video 4-4 (2022-02-28, 24:10): §4.4 Constructing string matching DFAs
    Chapters16:15 The Full Construction for the Kmp Dfa
    19:47 State Five
    23:02 Space Overhead
    23:53 The Knuthmore Spread Algorithm
  • Video 4-5 (2022-03-03, 27:03): §4.5 The Knuth-Morris-Pratt algorithm
    Chapters2:48 Example and mechanics
    5:50 Worst-case analysis
    8:44 Pseudocode implementation
    11:48 Complexity proof
    14:23 Computing failure links
    19:48 KMP performance review
    23:55 Prefix functions
  • Video 4-6 (2022-03-03, 22:38): §4.6 The Boyer-Moore algorithm
    Chapters0:14 Motivation
    5:12 Boyer-Moore Algorithm - Code
    6:45 Bad character examples
    9:15 Last-Occurrence Function Preprocess pattern Pand alphabet
    11:01 Good suffix examples
    16:03 Boyer-Moore algorithm - Discussion
    21:14 Clicker Question
  • Video 4-7 (2022-03-03, 16:47): §4.7 The Rabin-Karp algorithm
    Chapters1:31 Rabin-Karp Fingerprint Algorithm - Idea
    5:03 Rabin-Karp Fingerprint Algorithm - First Attempt
    7:33 Rabin-Karp Fingerprint Algorithm - Fast Rehash
    10:16 Rabin-Karp Fingerprint Algorithm - Code
    12:18 Rabin-Karp - Discussion
    14:52 Clicker Question
    15:53 String Matching Conclusion

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