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.
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
To build the Boyer-Moore last table, you need to determine the last occurrence of each character in the pattern. Here's how you can build the table for each pattern/alphabet pair:
(a) "giggling" - {g, I, l, n}
To build the last table for this pattern, you need to find the rightmost occurrence of each character in the pattern. Starting from the last character of the pattern, you can assign the index of the last occurrence of that character to its corresponding position in the last table. If a character in the pattern does not appear to the left of the current index, you can assign -1 to its position in the table. Here's the last table for this pattern:
Character: g I l n
Last index: 5 -1 4 -1
(b) "mimimi" - {i, m}
Similarly, to build the last table for this pattern, find the rightmost occurrence of each character. Here's the last table for this pattern:
Character: i m
Last index: 6 5
For the next part of the question:
14. Search for the pattern "pie" in the text "pickled peppers" and create a table like the one used in Example 4.31 to count hits and misses.
(a) Obvious algorithm:
The obvious algorithm for pattern matching involves scanning through the text one character at a time and comparing it with the pattern. If a mismatch occurs, the algorithm moves to the next character in the text. To count hits and misses, create a table with two columns: one for recording hits and another for misses. For each comparison made, mark whether it was a hit or a miss. Here's an example of such a table for this search:
Text position: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Text character: p i c k l e d p e p p e r s
Matching step: M M M H M M M M M M M M M M
In this example, there is one hit (misspelled as "H") at position 4, and the rest are misses (marked as "M").
(b) KMP algorithm:
The Knuth-Morris-Pratt (KMP) algorithm is an efficient algorithm for pattern matching. It constructs a table to avoid unnecessary comparisons by taking advantage of previous pattern matches. To count hits and misses, you can create a table similar to the one used for the obvious algorithm. Here's an example of such a table for this search:
Text position: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Text character: p i c k l e d p e p p e r s
Matching step: M M M H M M M M M M M M M M
The KMP algorithm would result in the same table as the obvious algorithm in this case.
(d) Boyer-Moore with only the shift table:
The Boyer-Moore algorithm uses both the last table and the shift table for efficient pattern matching. However, if you are using only the shift table, the steps would be the same as the obvious algorithm. The shift table in Boyer-Moore is used to determine the amount to move the pattern when a mismatch occurs. Here's an example of the table for this search:
Text position: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Text character: p i c k l e d p e p p e r s
Matching step: M M M H M M M M M M M M M M
In this example, the shift table is not used as we are only considering Boyer-Moore with the shift table.