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):
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
And then it continues somewhere else with:
If, during the search stage, a mismatch occurs at position
i − 1of
L′(i) > 0, then the good suffix rule shifts
n − L′(i)places to the right, so that the
L′(i) - lengthprefix of the shifted P aligns with the
L′(i) - lengthsuffix of the unshifted
P. In the case that
L′(i) = 0, the good suffix rule shifts
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
z. Now that
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
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?