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:
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.
... and so on. This leads to 2 comparisons in each of the 4 shifts i.e. 8 comparisons.
Instead, the answer, and also my intuition, suggests 5 comparisons:
... 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 -
I would like help in correcting my understanding of the algorithm.