1
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ I don't understand your question. Why don't you just sit down with the pseudocode of the algorithm and the input you're interested in, and see how many comparisons it takes? The whole point of an algorithm is that you can just robotically follow the steps without even needing to understand what they're trying to achieve. $\endgroup$ – David Richerby Oct 9 '16 at 11:24
  • $\begingroup$ @DavidRicherby: You're right, I should have done that earlier. It was a silly oversight on my part and I understood the algorithm incorrectly - thus making the mistake. I'll answer my own, rather silly, question. Thanks for the nudge! $\endgroup$ – Islay Oct 9 '16 at 12:36
  • 2
    $\begingroup$ And thanks for posting the answer! Welcome to the site! $\endgroup$ – David Richerby Oct 9 '16 at 13:06
3
$\begingroup$

Both - attempt 1 and 2 - are incorrect executions of the Horspool's algorithm. After the first round of trying to match the pattern in the text:

001001001001
111

There are two comparisons made of which the second one 0 == 1 fails. Now, the shift is determined by the last character in the section of the text being matched i.e. shift value of 1 which is 1. The next search round looks like:

001001001001
-111

This has only one comparison 0 == 1 which fails. The shift is now decided by the value of shift value of 0 which is 3, thus making the next round as follows:

001001001001
----111

This also has only one comparison, just like the previous one resulting in another shift of 3. The next round is also the same, with one comparison.

The total now, correctly, stands at 5.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.