I'm confused in trying to solve the following problem:
Find the number of comparisons made by Horspool's string search algorithm in the following case:
String: 001001001001
Pattern: 111
Attempt 1
The shift table value for 0
as per the algorithm should be 3 i.e. length of the pattern, because 0
is not part of the pattern.
001001001001
111
001001001001
---111
... and so on. This leads to 2 comparisons in each of the 4 shifts i.e. 8 comparisons.
Attempt 2
Instead, the answer, and also my intuition, suggests 5 comparisons:
001001001001
111
001001001001
--111
001001001001
-----111
... and so on. 2 comparisons needed in the first run and only 1 in each of the following 3 shifts i.e. total of 5.
Intuitively, it makes sense NOT to slide along the pattern 3 spaces [attempt 1] in the first run of the algorithm because we are not taking into account that the first character of the pattern - 1
- is the same as the last character of our previous string match block - 001
.
I would like help in correcting my understanding of the algorithm.