Chapter 5 Matching Algorithms
PREREQUISITES
Before beginning this chapter, you should be able to- Create finite automata
- Use character strings
- Use one- and two-dimensional arrays
- Describe growth rates and order
GOALS
At the end of this chapter, you should be able to- Explain the substring matching problem
- Explain the straightforward algorithm and its analysis
- Explain the use of finite automata for string matching
- Construct and use a Knuth-Morris-Pratt automaton
- Construct and use slide and jump arrays for the Boyer-Moore algorithm
- Explain the method of approximate string matching
STUDY SUGGESTIONS
As you are working through the chapter, you should rework the examples to
make sure you understand them. Using the string “abccbaabcabcbccabc” as the