# Understanding Boyer-Moore Algorithm

Edit: I've found the original publication. It seems to me that the original does not have a `l′(i)`. But I could be wrong because the definition of `rpr(i)` is so obscure to me. I'm not sure how it makes use of it when `rpr(i)` is negative and what happens when no such reoccurrence is found.

I'm trying to implement Boyer-Moore algorithm according to this. I'm not sure if it is part of a book or if it's just some university notes. According to it (just before Theorem 0.2.4):

Definition: Let `l′(i)` denote the length of the largest suffix of `P[i..n]` that is also a prefix of `P`, if one exists. If none exists, then let `l′(i)` be zero.

And then it continues somewhere else with:

If, during the search stage, a mismatch occurs at position `i − 1` of `P` and `L′(i) > 0`, then the good suffix rule shifts `P` by `n − L′(i)` places to the right, so that the `L′(i) - length` prefix of the shifted P aligns with the `L′(i) - length` suffix of the unshifted `P`. In the case that `L′(i) = 0`, the good suffix rule shifts `P` by `n − l′(i)` places.

Note that the rules work correctly even when `l′(i) = 0`.

Beware that indices are 1-based.

The part I'm having trouble with is the bold one. For example if we have the pattern `abcde` for which `l′(5) = 0` and if we test this against `abcze`; the first mismatch occurs on `d` vs `z`. Now that `l′(5)` is `0`, we need to shift it `n - l′(5)` characters to the right and thus lost our chance to find the matching. Edit: WRONG. It should really shift `n - l′(5)` characters because there is no `z` or `e` in the pattern prior to the character we're checking.

So I'm wondering if I'm missing something or not. Should I ignore `l′(i)` when it's zero?

So, after working on the algorithm a little more I got it working. The answer to my question is:

It should be shifted `n - l′(i)` characters to the right even when `l′(i) = 0`.

When `l′(i)` is zero, that means the following:

1. `L′(i)` is zero. So no reoccurring substring was found to the left that has a differing previous character. E.g:

``````mismatch:               v -----
pattern: a b c Z a b c Z a b c
index: 1 2 3 4 5 6 7 8 9 0 1
0                 1
``````

A mismatch occurs on `Z`. There is a reoccurring substring `abc` to the left, but it starts with `Z` too. So it's no good. `L′(9)` is `0`.

In this case, `abc` matches the prefix of the whole pattern, `abc`. `l′(9) = 3` which is length of the longest substr-prefix match.

`n - l′(9) = 11 - 3 = 8` shifts let us continue checking `pattern[1..3]` against already matched `abc` in the original text.

1. Pattern has no prefix that matches the already matched substring so far.

So it is impossible to find a matching unless we shift `n - l′(i) = n` characters to the right. I'm still not sure how the original publication handles the case when `L′(i)` is zero though.