Can't wrap my head around on building a suffix table for Boyer Moore 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 &quot;ABCBAB&quot; is the following:




k
suffix
d2




1
B
2


2
AB
4


3
BAB
4


4
CBAB
4


5
BCBAB
4




and for &quot;DRIDI&quot;:




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 &quot;BCBAB&quot;?), where as in the second table for k = 4, we cannot do the same (match D with the D inside the suffix &quot;RIDI&quot;), hence why the value for d2 is the length of the pattern, i.e 5 and not 3.
What's going on here?
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.
&quot;In the first table, for k = 5, we have d2 = 4.&quot; This is because &quot;AB&quot; is both a prefix of &quot;ABCBAB&quot; and a suffix of &quot;BCBAB&quot;. So if some text contains &quot;BCBAB&quot;, it is possible that text extends to right to contain &quot;BCBABCBAB&quot;, thus containing the pattern &quot;ABCBAB&quot;. It is not simply because 'we match the A with the suffix &quot;BCBAB&quot;'. 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 &quot;RIDI&quot;, 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