3/19

Question 1

Horspool’s Algorithm

Answer 1

1. Create a hash table from a string by working backwards from 2nd to last char and assigning ascending shift values starting at 1. Repeat letters (keys) have the same value. Letters that don’t appear have shift value m (length of pattern)
2. Compare the pattern (right to left) to the text (left to right). Let c be the first/rightmost character we compared. When we find a mismatch, shift using c’s shift value corresponding to the table.

Question 2

Boyer-Moore Algorith

Answer 2

1. Create TWO tables: a bad-symbol table (just like horspool’s) and a good-suffix table.
   If c is a mismatch, use bad-symbol table/shift past c.
2. If there is a match with the suffic, we can use good-suffix table/shift to a prefix that matches the suffix
3. Get max from the two above numbers and shift by that amount.

More space, less time

Question 3

Hashing

Answer 3

Efficient method of implementing a dictionary w/ operations find, insert, and delete.