1
$\begingroup$

My resources were the following video, as well as this video.

Basically, in one of the videos they state that the good suffix table for the pattern "ABCBAB" is the following:

k suffix d2
1 B 2
2 AB 4
3 BAB 4
4 CBAB 4
5 BCBAB 4

and for "DRIDI":

k suffix d2
1 I 2
2 DI 5
3 IDI 5
4 RIDI 5

If all of the above is correct, I can't understand why in the first table, for k = 5, we have d2 = 4 (because we match the A with the suffix "BCBAB"?), where as in the second table for k = 4, we cannot do the same (match D with the D inside the suffix "RIDI"), hence why the value for d2 is the length of the pattern, i.e 5 and not 3.

What's going on here?

$\endgroup$

1 Answer 1

1
$\begingroup$

The shift rules of Boyer–Moore algorithm come from the bad character rule and the good suffix rule.

While the bad character rule exploits a single character that is in the text but not in the pattern, the good suffix rule exploits multiple contiguous characters that appear in both the text and the pattern.

"In the first table, for k = 5, we have d2 = 4." This is because "AB" is both a prefix of "ABCBAB" and a suffix of "BCBAB". So if some text contains "BCBAB", it is possible that text extends to right to contain "BCBABCBAB", thus containing the pattern "ABCBAB". It is not simply because 'we match the A with the suffix "BCBAB"'. That B after A should be matched as well.

In the second table for k = 4, although we can match the D at the beginning with the D inside "RIDI", a shift of 3 cannot possibly match the whole pattern, since it will lead to the mismatch between the I after D and the R after D. So there is no need to consider a shift of 3.

          T:    ***RIDI̲***  
  current P:      DRIDI̲  
P shifted 3:         DR̲IDI  
$\endgroup$
2
  • $\begingroup$ Can you recommend any source for explaining how a good suffix table can be built, in laymen terms? It's much more complicated than I thought. $\endgroup$
    – SpiritBob
    Jan 27, 2021 at 11:14
  • $\begingroup$ By the "bad character rule", do you mean the bad character rule or the enhanced bad character rule? By the "good suffix rule", do you mean the good suffix rule or the strong good suffix rule? $\endgroup$ Sep 4 at 10:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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