String Matching (14)
John Reif
November 12th, 1998
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
Next:
STRING MATCHING
