```

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.

```

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.

```

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.

```

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.

```

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.
```

EXAMPLE
HERE IS A SIMPLE EXAMPLE

```
Another match! Click again.
```

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.

```

MPLEXAMPLE
HERE IS A SIMPLE EXAMPLE

```
We've aligned the `MPLE`s but focus on the end of the pattern.

Click on `P` to shift the pattern appropriately.

```

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.

```

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.

[end of example]