Here are some links to help you:
The Boyles-Moore 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
Pattern Matching
6. Build the Boyer-Moore 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 Boyer-Moore with only the shift table.
1 answer
1 answer