3 ms·
But instead, let's say we start off by hopping ahead 5 positions and instead look for the "s" at the end of "pen1s". Of course we don't find it, but then instea
by tlrobinson 19y ago
But instead, let's say we start off by hopping ahead 5 positions and instead look for the "s" at the end of "pen1s". Of course we don't find it, but then instead of checking the next spot, we again skip ahead 5 and look for "s". In fact, because we'll get zero matches, we can skip ahead 5 each time.
XXXXXXXXXXXXXXXXXXXXXXX
^ ^ ^ ....
s? s? s? ...
if we don't find the 's' in any of those positions, that immediately rules out the possibility that "pen1s" precedes it.
So instead of 1000 comparisons - we only do 200 !
Uhhh, no... consider the string to be searched:
Xpen1sXXXXXXXXXXXXXXXXX
^ ^ ^ ....
s? s? s? ...
Obviously you can't just skip 5 characters just because there's no "s" at position 5. The Boyer-Moore algorithm says you can skip those 5 characters because there's no X in the target string.
- henryw 19y ago"The algorithm has more complexity to it than I've illustrated (like what happens if you encounter an 'e' in one of the hops?) ..."
- tlrobinson 19y agoHis statement is still incorrect.
- mojuba 19y agoAgreed, I, too, had the feeling that he didn't get the algorithm. In fact, you have to compare every 5th position with all 5 letters of the pattern - p, e, n, 1 and s, (edit) or the other way around, like you said, which can be done nicely by using character sets like in Pascal or bitmaps in C++. Which brings up a question whether this method is any better than, for example, the Intel x86 instruction for linearly scanning strings (the SCAS family, if I'm not mistaken).