String Matching (17)
John Reif
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
