CODEWITHSUNDEEP
javacalgorithm
bjwg
bjwg

Reputation: 11

Boyer-Moore String Search algorithm starting alignments

I'm not a professional programmer, so pls bear with me. I'm looking around for reasons as to why the initial 'alignment' of haystack and needle should not be made at the first congruence of the needle's last character with the same one in the haystack, but at the earliest that being sought at needle.length()-1, rather than enforcing a comparison at 'haystack.needle.length()-1' and 'needle.length()-1' ?

Example :-

haystack : actuateaaaaaat

needle : descant

Above, everything before the final 't' in haystack can be completely ignored, in terms of shifts and comparisons theretofore.

Upvotes: 1

Views: 99

Answers (1)

rici
rici

Reputation: 241931

If you were to try to find the first t in the haystack (starting at the seventh character), you would have to look at every character in the haystack until the end.

Boyer Moore finds the position with many fewer comparisons. For example, after comparing t with e, it can move forward five characters. So the next comparison will be between the t and the second last a, and that will lead to a displacement of two. So the correct alignment is found after just two comparisons instead of seven.

Upvotes: 3

Related Questions