String Matching (14)

Greg Keim

October 28th, 1997

• STRING MATCHING
  • Matching Strings
  • Alphabets
  • Notation
  • The String Matching Problem
  • Extensions
• NAIVE PATTERN MATCHER
  • Examples
  • Algorithm
  • Analysis
  • More Analysis
  • Intuition for Improvement
• BOYER-MOORE
  • Naive Algorithm Again
  • Boyer-Moore Algorithm
  • Bad-Character Heuristic
  • Bad-Character Heuristic Analysis
  • Bad-Character Heuristic Algorithm
  • When does it help?
  • Good-Suffix Heuristic
  • Prefix Function
  • Computing the Prefix Function
  • Similarity Relation
  • Good-Suffix Heuristic
  • Good-Suffix Heuristic Algorithm
  • Analysis of Compute-Good-Suffix-Function
  • Analysis of Boyer-Moore
• STRING MATCHING WITH FINITE AUTOMATA
  • Finite Automata
  • Example
  • The Suffix-Function
  • String-Matching Automata
  • Finite-Automaton-Matcher
  • Computing the transition function
• HOMEWORK
  • Homework 7
  • Homework 8 (Incomplete)