4

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?

2

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.