Boyer-Moore Fast String Searching Example

 EXAMPLE
 HERE IS A SIMPLE EXAMPLE 

By fetching the S underlying the last character of the pattern we gain more information about matches in this area of the text.

• We are not standing on a match (because S isn't E).
• We wouldn't find a match even if we slid the pattern down by 1 (because S isn't L).
• We wouldn't find a match even if we slid the pattern down by 2 (because S isn't P).
• Etc.

In general, since S doesn't occur in the pattern at all we can slide the pattern down by its own length without missing a match. This will align the S we just found with an imaginary one just beyond the front of the pattern. This shift can be precalculated for every element of the alphabet and stored in a table.

Click on the S to slide the pattern down.

[Abort Search]

 SEXAMPLE
HERE IS A SIMPLE EXAMPLE 

Note we aligned the character S with its (imaginary) mate in the pattern.

But focus your attention again at the right end of the pattern.

Click on the P to shift the pattern down to align it with the P in the pattern.

[Abort Search]

 EXAMPLE
HERE IS A SIMPLE EXAMPLE 

We aligned the P's, but focus on the end.

Observe that the two red characters match. We may have found our pattern!

Click on the E to check the previous character.

[Abort Search]

 EXAMPLE
HERE IS A SIMPLE EXAMPLE 

Another match! We have to keep moving backwards. Note that we're about to look at the P again!

Click again.

[Abort Search]

 EXAMPLE
HERE IS A SIMPLE EXAMPLE 

Another match! Note that this is the second time we've fetched this P. That makes analysis of the worst case performance hard. But click again to check the previous character.

[Abort Search]

 EXAMPLE
HERE IS A SIMPLE EXAMPLE 

Another match! Click again.

[Abort Search]

 I
 MPLEXAMPLE
HERE IS A SIMPLE EXAMPLE 

Ok, something interesting!

The I we just fetched does not match its counterpart in the pattern (A). We could shift the pattern down to match our just discovered I with the imaginary one preceding the pattern.

But we can do better. We have discovered that MPLE occurs in the text. So we can shift the pattern down to align this discovered occurrence with its last occurrence in the pattern (which is partly imaginary). There are only seven terminal substrings of the pattern, so we can precompute all these shifts too and store them in a table.

In general the algorithm always has a choice of two shifts it could make and it takes the larger of the two.

Click on the MPLE to make this move.

[Abort Search]

 MPLEXAMPLE
HERE IS A SIMPLE EXAMPLE 

We've aligned the MPLEs but focus on the end of the pattern.

Click on P to shift the pattern appropriately.

[Abort Search]

 EXAMPLE
HERE IS A SIMPLE EXAMPLE 

We may have match. Click on the E to check the previous character. In fact, we have found the pattern and repeated comparisons confirm it. We don't make you do them all.

But click on the E to finish.

[Abort Search]

 EXAMPLE
HERE IS A SIMPLE EXAMPLE

Observe that we found the pattern without looking at all of the characters we scanned past. The longer the pattern is, the faster we move, on the average.

[Return to String Searching Page]







































[end of example]