CODEWITHSUNDEEP
algorithmstring-searchboyer-moore
Hawk
Hawk

Reputation: 5170

Shift rules in Boyer-Moore algorithm

There is something I could not figure out about the two shifting rules (bad character and good suffix) in this algorithm. Are they working together and what exactly decide which one to deploy in each case or shift. This comprehensive explanation ended with an example of SSIMPLE EXAMPLE which confused me, my question here, if the algorithm moves backward, why would the algorithm will need good suffix shift to move to the right? I am sure I miss something here. Would you help me to explain the aforementioned example.

Upvotes: 1

Views: 306

Answers (1)

Hawk
Hawk

Reputation: 5170

The missing point is the algorithm moves backward on the pattern not the string, so the comparison starts from the character of index n ( n is pattern length) not from the index 1. the following visual example is very helpful to clarify that.

Upvotes: 1

Related Questions