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
$\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$
1
  • $\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 at 11:14

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.