By fetching theEXAMPLE HERE I A SIMPLE EXAMPLE

`S`

- We are not standing on a match (because
isn't`S`

).`E`

- We wouldn't find a match even if we slid the pattern down by 1 (because
isn't`S`

).`L`

- We wouldn't find a match even if we slid the pattern down by 2 (because
isn't`S`

).`P`

- Etc.

`S`

`S`

Click on the ** S** to slide the
pattern down.

Note we aligned the characterSEXAMLE HERE IS A SIMLE EXAMPLE

`S`

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`

We aligned theEXAMPL HERE IS A SIMPL EXAMPLE

`P`

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

Click on the ** E** to check the previous character.

Another match! We have to keep moving backwards. Note that we're about to look at the P again!EXAMPE HERE IS A SIMPE EXAMPLE

Click again.

Another match! Note that this is the second time we've fetched thisEXAMLE HERE IS A SIMLE EXAMPLE

`P`

Another match! Click again.EXAPLE HERE IS A SIPLE EXAMPLE

Ok, something interesting!I XAMPLE HERE IS A SI EXAMPLE

The ** I** we just fetched does not
match its counterpart in the pattern (

`A`

`I`

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.

We've aligned theMPLEXAMLE HERE IS A SIMPLE EXAMLE

`MPLE`

Click on ** P** to shift the pattern appropriately.

We may have match. Click on theEXAMPL HERE IS A SIMPLE EXAMPL

`E`

But click on the ** E** to finish.

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.HERE IS A SIMPLE

[Return to String Searching Page]

[end of example]