The Boyer$-$Moore algorithm

Step $1$ For a given pattern and the alphabet used in both the pattern and the

text, construct the bad$-$symbol shift table as described earlier.

$//$Use the table creator function you creted for Horspool$$s

Step $2$ Using the pattern, construct the good$-$suffix shift table as described

earlier.

int $*$GoodSuffixTable$($char $*$needle$,$ int $*$gsuffix$)$

$\{$

$//$ Your code here

for$($i$=1$; i$=0$ character

pairs are matched successfully. In the latter case, retrieve the entry

t$1($c$)$ from the c$$s column of the bad$-$symbol table where c is the text$$s

mismatched character. If k $>0,$ also retrieve the corresponding d$2$

entry from the good$-$suffix table. Shift the pattern to the right by the number of positions computed by the formula

if k $=0$

d $=$ d$1$

if m $>$ k $>0$

d $=$ max$\{$d$1,$ d$2\}$

if k$==$m

match found!

d$=1$

where d$1=$ max$\{$t$1($c$)$ k$,1\}.$

Shifting by the maximum of the two available shifts when k $>0$ is quite logical$.$

The two shifts are based on the observations$$the first one about a text$$s

mismatched character, and the second one about a matched group of the pattern$$s

rightmost characters$$that imply that shifting by less than d$1$ and d$2$ characters, respectively,

cannot lead to aligning the pattern with a matching substring in the text.

Since we are interested in shifting the pattern as far as possible without missing a

possible matching subs

$1$ b $2$

$2$ ab $5$

$3$ bab $5$

$4$ obab $5$

$5$ aobab $5$

bess$\_$knew$\_$about$\_$baobabs

baobab

baobab d$1=4$ d$2=5$

baobab d$1=5$ d$2=2$

baobab$---$found

baobab

Matches found at locations: $16$