Question

Part a: (20 points) Apply Horspool's algorithm to search for the pattern BAOBAB in the text BESS KNEW ABOUT BAOBABS. (In each shift, you need to specify which of those four rules has been applied.) Part b: (20 points) Draw a shift table and calculate the shift value for cach character.

Answer 1

Horspool's algorithm is a string searching algorithm used to find occurrences of a pattern within a larger text. To apply Horspool's algorithm to search for the pattern BAOBAB, we need to create a shift table, determine the shift values, and compare the pattern with the text. The shift table for BAOBAB is B:6, A:5, O:4, B:3, A:2, B:1.

Step-by-step explanation:

Horspool's algorithm is a string searching algorithm that is used to find occurrences of a pattern within a larger text. To apply Horspool's algorithm to search for the pattern BAOBAB in the text BESS KNEW ABOUT BAOBABS, we need to follow the following steps:

1. Create a shift table that determines the amount to shift the pattern based on the mismatched character.
2. Initialize the shift value to the pattern length.
3. Compare the last character of the pattern with the current character in the text.
4. If a match is found, compare the previous characters of the pattern and text.
5. If the pattern is found, return the index of the first occurrence.
6. If the pattern is not found, determine the shift value and move the pattern to the right by that value.
7. Repeat steps 3-6 until the pattern is found or the end of the text is reached.
8. Shift Table and Shift Values

The shift table determines how much to shift the pattern based on the mismatched character. Here is the shift table for the pattern BAOBAB:

Character Shift Value

B 6

A 5

O 4

B 3

A 2

B 1

When searching for the pattern BAOBAB in the text BESS KNEW ABOUT BAOBABS, we start comparing the last character of the pattern with the current character in the text. If a mismatch occurs, we consult the shift table to determine the shift value. In this case, the first mismatch is between the last character of the pattern (B) and the character in the text (S). Therefore, we shift the pattern 6 positions to the right and continue comparing.

Answer 2

Horspool's algorithm utilizes a shift table that determines the number of positions to shift the pattern for each mismatch.

Here's the shift table and the calculation of shift values for each character in the pattern "BAOBAB" while searching in the text "BESS KNEW ABOUT BAOBABS":

Shift Table:

Character Shift Value

B 4

A 5

O 2

Calculation of Shift Values:

For each character in the pattern "BAOBAB," calculate the shift value based on its position from right to left:

For character 'B':

No other 'B' exists in the pattern, so the shift value for 'B' is the length of the pattern - 1 = 6 - 1 = 5.

For character 'A':

No other 'A' exists in the pattern, so the shift value for 'A' is the length of the pattern = 6.

For character 'O':

The rightmost 'O' has one occurrence in the pattern, so the shift value for 'O' is 2.

For character 'B':

The rightmost 'B' has one occurrence in the pattern, so the shift value for 'B' is 4.