Discrete Math
posted by JayLQue on .
Pattern Matching
6. Build the BoyerMoore last table for the following pattern/alphabet pairs.
(a) “giggling”’ {g, I, l, n}
(b) “mimimi” , {i, m}
(b) ANSWER: i m
6 5
14. Search for the pattern “pie” in the text “pickled peppers”.
Create a table like that used in Example 4.31 and count hits and misses.
Graph paper would be helpful.
(a) Use the obvious algorithm.
(b) Use the KMP algorithm.
(d) Use BoyerMoore with only the shift table.

Here are some links to help you:
The BoylesMoore algorithm
http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm
KMP algorithm:
http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm